1 5 5 14 S*#*. .#... ..... ****. ...#. ..*.P #.*.. ***.. ...*. *.#..
YES
#include <iostream> #include<cstdio> #include<cstring> #include<queue> using namespace std; struct node { int x,y,z; //记录位置 int ti; //记录访问当前点的时间 }; int dr[4][2]={{1,0},{0,1},{-1,0},{0,-1} };//上下左右四个方向 char mp[2][11][11]; //记录迷宫 int n,m,t,c,i,j,tx,ty,tz,k; int bfs() { node p; p.x=0; p.y=0; p.z=0; p.ti=0; //在(0,0,0)点出发 queue<node> s; s.push(p); mp[0][0][0]=‘*‘; // 标记走过 while(!s.empty()) { node q=s.front(); s.pop(); for(i=0;i<4;i++) { int xx=q.x+dr[i][0]; int yy=q.y+dr[i][1]; int zz=q.z; if(xx>=0 && xx<n && yy>=0 && yy<m && mp[zz][xx][yy]!=‘*‘) { if(mp[zz][xx][yy]==‘#‘) //遇到时空传输机，到另一层相对位置 { mp[zz][xx][yy]=‘*‘; //没换层前的位置标记走过 zz=(zz+1)%2; //换层 } mp[zz][xx][yy]=‘*‘; p.x=xx; p.y=yy; p.z=zz; p.ti=q.ti+1; s.push(p); if (p.ti>t) return 0; if (zz==tz && yy==ty && xx==tx) return 1; } } } return 0; } int main() { scanf("%d",&c); for(;c>0;c--) { scanf("%d%d%d",&n,&m,&t); for(k=0;k<=1;k++) //读入 0层和1层 for(i=0;i<n;i++) { scanf("%s",&mp[k][i]); for(j=0;j<m;j++) if(mp[k][i][j]==‘P‘) tx=i,ty=j,tz=k; //记录公主位置 } for(i=0;i<n;i++) //预处理 for(j=0;j<m;j++) { char a=mp[0][i][j]; char b=mp[1][i][j]; if (a==‘#‘ && b==‘*‘ || a==‘*‘ && b==‘#‘ || a==‘#‘ && b==‘#‘) mp[0][i][j]=mp[1][i][j]=‘*‘; } if( bfs() ) printf("YES\n"); else printf("NO\n"); } return 0; }
原文：http://www.cnblogs.com/stepping/p/5669079.html