@xunuo
2017-04-21T19:37:55.000000Z
字数 2222
阅读 995
Time Limit: 3000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
BFS
可怜的公主在一次次被魔王掳走一次次被骑士们救回来之后,而今,不幸的她再一次面临生命的考验。魔王已经发出消息说将在T时刻吃掉公主,因为他听信谣言说吃公主的肉也能长生不老。年迈的国王正是心急如焚,告招天下勇士来拯救公主。不过公主早已习以为常,她深信智勇的骑士LJ肯定能将她救出。
现据密探所报,公主被关在一个两层的迷宫里,迷宫的入口是S(0,0,0),公主的位置用P表示,时空传输机用#表示,墙用*表示,平地用.表示。骑士们一进入时空传输机就会被转到另一层的相对位置,但如果被转到的位置是墙的话,那骑士们就会被撞死。骑士们在一层中只能前后左右移动,每移动一格花1时刻。层间的移动只能通过时空传输机,且不需要任何时间。
输入的第一行C表示共有C个测试数据,每个测试数据的前一行有三个整数N,M,T。 N,M迷宫的大小N*M(1 <= N,M <=10)。T如上所意。接下去的前N*M表示迷宫的第一层的布置情况,后N*M表示迷宫第二层的布置情况。
如果骑士们能够在T时刻能找到公主就输出“YES”,否则输出“NO”。
1
5 5 14
S*#*.
.#...
.....
****.
...#.
..*.P
#.*..
***..
...*.
*.#..
YES
解题思路:
一个BFS,但是要注意的是...他是一个三维的!!!!!它有两层楼。。。。
还有:只要遇到'#'都要传送;所以就可以特判一下:当当前位置为'#'且传送到的位置也是'#'或者是墙('*')时就将这个位置和传送的位置变为墙('*');
还有就是在vis初始化的时候要....唉。。。。
完整代码:
#include<bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
int dir[4][2]={0,1,0,-1,1,0,-1,0};
int vis[15][15][2];
char a[2][15][15];
int n,m,t;///n行m列t秒
int ans,flag;
struct node
{
int x,y,z;
int t;
};
int bfs()
{
queue<node>q;
node now,next;
now.x=0,now.y=0;
now.z=0,now.t=0;
flag=0;
q.push(now);
vis[now.x][now.y][now.z]=1;
for(int i=0;i<2;i++)
for(int j=0;j<n;j++)
for(int k=0;k<m;k++)
{
if(i==0&&a[0][j][k]=='#'&&(a[1][j][k]=='*'||a[1][j][k]=='#'))
{
a[0][j][k]='*';
a[1][j][k]='*';
}
if(i==1&&a[1][j][k]=='#'&&(a[0][j][k]=='*'||a[0][j][k]=='#'))
{
a[0][j][k]='*';
a[1][j][k]='*';
}
}
while(!q.empty())
{
now=q.front();
q.pop();
if(a[now.z][now.x][now.y]=='P')
{
ans=now.t;
break;
}
for(int i=0;i<4;i++)
{
next.x=now.x+dir[i][0];
next.y=now.y+dir[i][1];
next.z=now.z;
if(a[next.z][next.x][next.y]=='#'&&vis[next.x][next.y][next.z]==0)
{
if(next.z==0&&vis[next.x][next.y][next.z+1]==0)
{
vis[next.x][next.y][next.z]=1;
next.t=now.t+1;
next.z+=1;
flag=1;
}
else if(next.z==1&&vis[next.x][next.y][next.z-1]==0)
{
vis[next.x][next.y][next.z]=1;
next.t=now.t+1;
next.z-=1;
flag=1;
}
}
if(a[next.z][next.x][next.y]!='*'&&vis[next.x][next.y][next.z]==0&&next.x>=0&&next.y>=0&&next.x<n&&next.y<m)
{
if(flag==1)
flag=0;
else
next.t=now.t+1;
q.push(next);
vis[next.x][next.y][next.z]=1;
}
}
}
return ans;
}
int main()
{
int c;
scanf("%d",&c);
while(c--)
{
scanf("%d%d%d",&n,&m,&t);
for(int j=0;j<2;j++)
{
for(int i=0;i<n;i++)
{
scanf("%s",a[j][i]);
for(int k=0;k<m;k++)
vis[i][k][j]=0;
}
}
ans=inf;
if(bfs()<=t)
printf("YES\n");
else
printf("NO\n");
}
return 0;
}