转载请注明出处：

题目链接：

Problem Description

可怜的公主在一次次被魔王掳走一次次被骑士们救回来之后，而今，不幸的她再一次面临生命的考验。魔王已经发出消息说将在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

比較坑的地方：

/*1.碰到'#'传送们必传送，没有另外一种选择。

2.有可能起点和终点在同一层，例子是分别在两层里。起点和终点能够在随意的位置。

3.两边都是传送门时，或者一边是传送门一边是墙时，这两种情况是死路。

4.输入时要注意两张地图间有空行，要特殊处理。

*/

代码例如以下：

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          using namespace std;#define M 17int xx[4]={1,0,0,-1};int yy[4]={0,1,-1,0};int x,y,z;int n, m, ttime;char map[2][M][M];int vis[2][M][M];//标记struct node{	int x, y, z;	int Time;};//q.push(front);void bfs(){	int i;	int dx, dy, dz;	queue
          
           q; node front, rear; memset(vis,0,sizeof(vis)); front.x = x,front.y=y,front.z=z; front.Time = 0; vis[z][x][y] = 1; q.push(front);//若这个定义在外面则必须每次清空 while(!q.empty()) { front = q.front(); q.pop(); for(i = 0; i < 4; i++) { dx = front.x+xx[i]; dy = front.y+yy[i]; dz = front.z; //推断是否越界，目标点是否为墙，是否超时 if(dx>=0&&dx
           
            =0&&dy
            
             > n >> m >> ttime; for(k = 0; k < 2; k++) { for(i = 0; i < n; i++) { // scanf("%s",map[k][i]); for(j = 0; j < m; j++) { cin>>map[k][i][j]; if(map[k][i][j] == 'S') { x = i, y = j, z = k; } } } } for(i = 0; i < n; i++) { for(j = 0; j < m; j++) { if(map[0][i][j]=='#' && map[1][i][j]=='*') {//假设传送机上方是墙，他就会撞死。。。。 //所以这样的情况也要排除。 map[0][i][j] = '*'; } if(map[0][i][j]=='*' && map[1][i][j]=='#') {//假设传送机下方是墙，相同他会撞死，也排除 map[1][i][j] = '*'; } if(map[0][i][j]=='#' && map[1][i][j]=='#') {//假设传送机上方还是传送机，就会陷入死循环， //所以这样的情况我们把上下相应的两个位置设为墙． map[0][i][j] = '*',map[1][i][j] = '*'; } } } bfs(); } } return 0;}