title: A计划（三维广搜）
tags: [杭电,ACM,广搜]
分析
三维的搜索题，在二维的基础上增加一个层数，当走到传输门时会自动的跑到另外的一层 思路还是普通的广搜，注意传输门之后的情况，有可能传输过去是一堵墙，或者还是一个传输门。
代码中有详细的注解：
#include<stdio.h>
#include<queue>
#include<string.h>
using namespace std;
int n,m,t,op=0;
char tu[2][15][15];
int dir[4][2]= {1,0,0,1,-1,0,0,-1};
int vist[2][15][15];
struct Node
{
int x;
int y;
int z;//层数
int s;
};
void bfs(int x,int y,int z)
{
memset(vist,0,sizeof(vist));
Node node;
node.x=x;
node.y=y;
node.z=z;
node.s=0;
vist[node.z][node.x][node.y]=1;
queue<Node>q;
q.push(node);
Node temp;
while(!q.empty())
{
node=q.front();
q.pop();
if(tu[node.z][node.x][node.y]=='P'&&node.s<=t)//在规定的时间内到达地点
{
op=1;
return;
}
for(int i=0; i<4; i++)
{
temp.x=node.x+dir[i][0];
temp.y=node.y+dir[i][1];
temp.z=node.z;//当前所在的层数
temp.s=node.s+1;
if(temp.s>t)
continue;
if(temp.x<0||temp.y<0||temp.x>=n||temp.y>=m||vist[temp.z][temp.x][temp.y]==1||tu[temp.z][temp.x][temp.y]=='*')
continue;
if(tu[temp.z][temp.x][temp.y]=='#')
{
vist[node.z][temp.x][temp.y]=1;//将本次的传输门标记
temp.z=(node.z+1)%2;//到达另一层
if(vist[temp.z][temp.x][temp.y]==0)//如果传输过去的位置没有走过
{
vist[temp.z][temp.x][temp.y]=1;//标记走过
q.push(temp);//入队
}
}
if(tu[temp.z][temp.x][temp.y]=='.'||(tu[temp.z][temp.x][temp.y]=='P'))//如果为道路或者目标地点
{
vist[node.z][temp.x][temp.y]=1;//标记走过
q.push(temp);//入队
}
}
}
}
int main()
{
int count1;
scanf("%d",&count1);
while(count1--)
{
op=0;
scanf("%d%d%d",&n,&m,&t);
for(int k=0; k<2; k++)
for(int i=0; i<n; i++)
{
scanf("%s",tu[k][i]);
}
///当遇到传输门时会被传输到另一层与之相对应的地方，但是如果这个地方是墙的话，士兵就会死亡
///所以去掉这种情况，
//当相对应的地方是还是传输门时，会形成死循环 也要去掉这种情况
for(int i=0; i<n; i++)
for(int j=0; j<m; j++)
{
if(tu[0][i][j]=='#'&&(tu[1][i][j]=='*'||tu[1][i][j]=='#'))
{
tu[0][i][j]='*';
tu[1][i][j]='*';
}
if(tu[1][i][j]=='#'&&(tu[0][i][j]=='*'||tu[0][i][j]=='#'))
{
tu[0][i][j]='*';
tu[1][i][j]='*';
}
}
bfs(0,0,0);
if(op==1)
printf("YES
");
else printf("NO
");
}
return 0;
}