https://cn.vjudge.net/contest/254150#problem/F
wa代码：
#include<iostream>
#include<string>
#include<cstring>
#include<queue>
#include<stdio.h>
#include<stack>
#include<map>
#include<stack>
using namespace std;
# define maxn 100
char a[10][maxn][maxn];
int vis[maxn][maxn][maxn];
int n,m,k;
int f[2][4]= {{1,-1,0,0},{0,0,1,-1}};
struct node
{
int x,y,z,step;
node(int xx,int yy,int zz,int tt)
{
z=xx;
x=yy;
y=zz;
step=tt;
}
};
bool judge(int s1,int s2)
{
if(s1>=0&&s1<n&&s2>=0&&s2<m)return true;
return false;
}
bool bfs(int t1,int t2,int t3)
{
memset(vis,0,sizeof(vis));
queue<node>q;
while(!q.empty())q.pop();
q.push(node(t1,t2,t3,0));
vis[t1][t2][t3]=1;
while(!q.empty())
{
node temp=q.front();
q.pop();
if(a[temp.z][temp.x][temp.y]=='P')
{
if(temp.step<=k)
return true;
return false;
}
for(int i=0; i<4; i++)
{
int x=temp.x+f[0][i];
int y=temp.y+f[1][i];
if(judge(x,y)&&vis[temp.z][x][y]==0&&a[temp.z][x][y]!='*')
{
vis[temp.z][x][y]=1;
if(a[temp.z][x][y]=='#')
{
if(temp.z==0)
{
if(a[1][x][y]!='*'&&a[1][x][y]!='#'&&vis[1][x][y]==0)
{
q.push(node(1,x,y,temp.step));
vis[1][x][y]=1;
}
}
else if(temp.z==1)
{
if(a[0][x][y]!='*'&&a[0][x][y]!='#'&&vis[0][x][y]==0)
{
q.push(node(0,x,y,temp.step));
vis[0][x][y]=1;
}
}
}
else
{
q.push(node(temp.z,x,y,temp.step+1));
}
}
}
}
return false;
}
int main()
{
int T;
cin>>T;
while(T--)
{
int t1,t2,t3;
memset(a,'\n',sizeof(a));
cin>>n>>m>>k;
for(int i=0; i<2; i++)
{
for(int j=0; j<n; j++)
{
for(int l=0; l<m; l++)
{
cin>>a[i][j][l];
if(a[i][j][l]=='S'){
t1=i;
t2=j;
t3=l;
}
}
}
}
if(bfs(t1,t2,t3))
cout<<"YES"<<endl;
else
cout<<"NO"<<endl;
}
return 0;
}
AC代码：
#include<iostream>
#include<string>
#include<cstring>
#include<queue>
#include<stdio.h>
#include<stack>
#include<map>
#include<stack>
using namespace std;
# define maxn 15
char a[2][maxn][maxn];
int vis[maxn][maxn][maxn];
int n,m,k;
int f[2][4]= {{1,-1,0,0},{0,0,1,-1}};
struct node
{
int x,y,z,step;
node(int xx,int yy,int zz,int tt)
{
z=xx;
x=yy;
y=zz;
step=tt;
}
};
bool judge(int s1,int s2)
{
if(s1>=0&&s1<n&&s2>=0&&s2<m)return true;
return false;
}
bool bfs(int t1,int t2,int t3)
{
memset(vis,0,sizeof(vis));
queue<node>q;
while(!q.empty())q.pop();
q.push(node(t1,t2,t3,0));
vis[t1][t2][t3]=1;
while(!q.empty())
{
node temp=q.front();
q.pop();
if(a[temp.z][temp.x][temp.y]=='P')
{
if(temp.step<=k)
return true;
return false;
}
if(a[temp.z][temp.x][temp.y]=='#')//原来一直wa的原因就在这里，应该是先判断，再去跑四个方向，否则的话，如果先跑四个方向再去判断的话，这样步数就会少算一步。
{
if(temp.z==0)
{
if(a[1][temp.x][temp.y]!='*'&&a[1][temp.x][temp.y]!='#'&&vis[1][temp.x][temp.y]==0)
{
q.push(node(1,temp.x,temp.y,temp.step));
vis[1][temp.x][temp.y]=1;
}
}
else if(temp.z==1)
{
if(a[0][temp.x][temp.y]!='*'&&a[0][temp.x][temp.y]!='#'&&vis[0][temp.x][temp.y]==0)
{
q.push(node(0,temp.x,temp.y,temp.step));
vis[0][temp.x][temp.y]=1;
}
}
}
else
{
for(int i=0; i<4; i++)
{
int x=temp.x+f[0][i];
int y=temp.y+f[1][i];
if(judge(x,y)&&vis[temp.z][x][y]==0&&a[temp.z][x][y]!='*')
q.push(node(temp.z,x,y,temp.step+1)),vis[temp.z][x][y]=1;
}
}
}
return false;
}
int main()
{
int T;
cin>>T;
while(T--)
{
int t1,t2,t3;
memset(a,'\n',sizeof(a));
cin>>n>>m>>k;
for(int i=0; i<2; i++)
{
for(int j=0; j<n; j++)
{
for(int l=0; l<m; l++)
{
cin>>a[i][j][l];
if(a[i][j][l]=='S')
{
t1=i;
t2=j;
t3=l;
}
}
}
}
if(bfs(t1,t2,t3))
cout<<"YES"<<endl;
else
cout<<"NO"<<endl;
}
return 0;
}