A計劃

?HDU - 2102?

可憐的公主在一次次被魔王擄走一次次被騎士們救回來之后，而今，不幸的她再一次面臨生命的考驗。魔王已經發出消息說將在T時刻吃掉公主，因為他聽信謠言說吃公主的肉也能長生不老。年邁的國王正是心急如焚，告招天下勇士來拯救公主。不過公主早已習以為常，她深信智勇的騎士LJ肯定能將她救出。?
現據密探所報，公主被關在一個兩層的迷宮里，迷宮的入口是S（0，0，0），公主的位置用P表示，時空傳輸機用#表示，墻用*表示，平地用.表示。騎士們一進入時空傳輸機就會被轉到另一層的相對位置，但如果被轉到的位置是墻的話，那騎士們就會被撞死。騎士們在一層中只能前后左右移動，每移動一格花1時刻。層間的移動只能通過時空傳輸機，且不需要任何時間。

Input

輸入的第一行C表示共有C個測試數據，每個測試數據的前一行有三個整數N，M，T。 N，M迷宮的大小N*M（1 <= N,M <=10)。T如上所意。接下去的前N*M表示迷宮的第一層的布置情況，后N*M表示迷宮第二層的布置情況。

Output

如果騎士們能夠在T時刻能找到公主就輸出“YES”，否則輸出“NO”。

Sample Input

1
5 5 14
S*#*.
.#...
.....
****.
...#...*.P
#.*..
***..
...*.
*.#..

Sample Output

YES

這其實也是一道廣搜的模板題，就是有注意當在一層進入傳送門后到另一層不能也是傳送門，其他就是普通的模板

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstdlib>
#include <cstring>
#include <map>
#include <stack>
#include <queue>
#include <vector>
#include <bitset>
#include <set>
#include <utility>
using namespace std;
typedef long long ll;
#define inf 0x3f3f3f3
#define rep(i,l,r) for(int i=l;i<=r;i++)
#define lep(i,l,r) for(int i=l;i>=r;i--)
#define ms(arr) memset(arr,0,sizeof(arr))
/*priority_queue<int,vector<int> ,greater<int> >q;*/
const int maxn = (int)1e5 + 5;
const ll mod = 1e9+7;
char mapp[5][12][12];
bool vis[5][12][12];
int dx[4]={0,1,0,-1};
int dy[4]={1,0,-1,0};
int N,M,T;
struct node
{int x,y,z;int t;
}q[1000],a,b;
int bfs()
{q[0].x=1;q[0].y=1;q[0].z=1;q[0].t=0;vis[1][1][1]=true;int head=0,tail=1;while(head<tail){a=q[head];head++;rep(i,0,3) {b.x=a.x+dx[i];b.y=a.y+dy[i];b.z=a.z;b.t=a.t+1;if(b.t>T)return -1;if(mapp[b.z][b.x][b.y]=='#'){if(b.z==1)b.z=2;elseb.z=1;}if(b.x<1||b.x>N||b.y<1||b.y>M||mapp[b.z][b.x][b.y]=='*'||vis[b.z][b.x][b.y]==true||mapp[b.z][b.x][b.y]=='#')continue;else{vis[b.z][b.x][b.y]=true;q[tail]=b;tail++;if(mapp[b.z][b.x][b.y]=='P')return b.t;}}}return -1;
}
int main()?
{
/* ? ?freopen("in.txt", "r", stdin);freopen("out.txt", "w", stdout);*/ios::sync_with_stdio(0),cin.tie(0);int C;scanf("%d",&C);while(C--){char ch;ms(vis);ms(mapp);scanf("%d %d %d%c",&N,&M,&T,&ch);rep(i,1,2) {rep(j,1,N) {scanf("%s",mapp[i][j]+1);}}int time=bfs();if(time!=-1)cout<<"YES"<<endl;elsecout<<"NO"<<endl;}return 0;
}

?