可怜的公主在一次次被魔王掳走一次次被骑士们救回来之后，而今，不幸的她再一次面临生命的考验。魔王已经发出消息说将在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 #.*.. ***.. ...*. *.#..
#include<cstdio>
#include<cstring>
#include<queue>//队列
using namespace std;
const int maxn=14;
char maze[maxn][maxn][3];//地图
bool vis[maxn][maxn][3];//相当于book记录
int dx[4]= {0,0,-1,1};
int dy[4]= {1,-1,0,0};
int n,m,t;
struct Point {
int x,y,z,time;//x行，y列,z记录哪个地图.
};
void bfs() {
memset(vis,0,sizeof(vis));
queue<Point>que;
while(!que.empty()) que.pop();
Point ss;
ss.x=ss.y=1;
ss.z=0;
ss.time=0;
que.push(ss);
vis[1][1][0]=true;
while(!que.empty()) {
Point u=que.front();
que.pop();
if(u.time>t)
continue;
if(maze[u.x][u.y][u.z]==3) {
printf("YES\n");
return ;
}
for(int i=0; i<4; i++) {
Point du;
du.x=u.x+dx[i];
du.y=u.y+dy[i];
du.z=u.z;
du.time=u.time+1;
if(du.x<1||du.x>n||du.y<1||du.y>m)
continue;
if(vis[du.x][du.y][du.z])
continue;
if(!maze[du.x][du.y][du.z])
continue;
if(maze[du.x][du.y][du.z]==2) {
if((maze[du.x][du.y][!du.z])==0||vis[du.x][du.y][!du.z]
||maze[du.x][du.y][!du.z]==2)
continue;
du.z=!du.z;
que.push(du);
vis[du.x][du.y][du.z]=true;
vis[du.x][du.y][!du.z]=true;
} else {
que.push(du);
vis[du.x][du.y][du.z]=true;
}
}
}
printf("NO\n");
}
int main() {
int test;
scanf("%d",&test);
while(test--) {
scanf("%d%d%d",&n,&m,&t);
char str[maxn];
for(int l=0; l<2; l++) {
for(int i=1; i<=n; i++) {
scanf("%s",&str);
for(int j=1; j<=m; j++) {
if(str[j-1]=='#')
maze[i][j][l]=2;
else if(str[j-1]=='*')
maze[i][j][l]=0;
else if(str[j-1]=='.'||str[j-1]=='S')
maze[i][j][l]=1;
else if(str[j-1]=='P') {
maze[i][j][l]=3;
}
}
}
}
bfs();
}
return 0;
}
你有什么问题呢？
您好，我是有问必答小助手，您的问题已经有小伙伴解答了，您看下是否解决，可以追评进行沟通哦~
如果有您比较满意的答案 / 帮您提供解决思路的答案，可以点击【采纳】按钮，给回答的小伙伴一些鼓励哦～～
ps:问答VIP仅需29元，即可享受5次/月 有问必答服务，了解详情>>>https://vip.csdn.net/askvip?utm_source=1146287632