这不知道是公主被抓走了第几次了，反正我们的骑士救就对了（别说了，我都救我都救...）;这次的迷宫有些特别，双层，带电梯（？），而且这个电梯还有生命危险，可能会撞死（一层是电梯，一层是墙），或者永远困在电梯里（上下两层都是电梯），而且上了电梯必须移动，我想到的是BFS，WA了一次，主要是这题的细节问题比较多，认真处理一下就好；
代码如下:
RunId : 21313702 Language : C++ Author : hnustwanghe
Code Render Status : Rendered By HDOJ C++ Code Render Version 0.01 Beta
#include<iostream>
#include<cstring>
#include<cstdio>
#include<queue>
using namespace std;
const int N = 10 + 5;
const int INF = (1<<30);
char mat[2][N][N];
bool visit[2][N][N];
typedef struct node{
int x,y,z,val;
node(int x=0,int y=0,int z=0,int val=0):x(x),y(y),z(z),val(val){}
}Node;
Node goal;
int n,m,k;
const int dir[4][2]={{1,0},{-1,0},{0,1},{0,-1}};
bool BFS(){
queue<Node> Q;
int ans = INF;
Node t,s;
Q.push(Node(0,0,0));
visit[0][0][0] = true;
while(!Q.empty()){
t = Q.front();Q.pop();
if(t.x==goal.x && t.y == goal.y && t.z == goal.z && t.val<=k) { ans=min(ans,t.val);continue;}
for(int d=0;d<4;d++){
int newx = t.x + dir[d][0];
int newy = t.y + dir[d][1];
if(newx >= 0 && newx < n && newy >=0 && newy < m && !visit[t.z][newx][newy] && mat[t.z][newx][newy]!='*'){
if(mat[t.z][newx][newy]=='#' && !visit[t.z^1][newx][newy]){
s.x =newx,s.y= newy ,s.val = t.val+1,s.z = t.z^1;
visit[t.z^1][newx][newy] = visit[t.z][newx][newy] = true;
Q.push(s);
}else{
s.x = newx , s.y = newy,s.val = t.val+1,s.z = t.z;
visit[t.z][newx][newy] = true;
//if(t.val <= k)
Q.push(s);
}
}
}
}
return ans!=INF;
}
void solve_question(){
memset(visit,0,sizeof(visit));
for(int i=0;i<n;i++)
for(int j=0;j<m;j++){
if(mat[0][i][j]=='*' && mat[1][i][j]=='#') mat[0][i][j] = mat[1][i][j] = '*';
if(mat[0][i][j]=='#' && mat[1][i][j]=='*') mat[0][i][j] = mat[1][i][j] = '*';
if(mat[0][i][j]=='#' && mat[1][i][j]=='#') mat[0][i][j] = mat[1][i][j] = '*';
}
printf("%s\n",BFS()?"YES":"NO");
}
int main(){
int T;
scanf("%d",&T);
while(T--){
scanf("%d %d %d",&n,&m,&k);
for(int k=0;k<2;k++)
for(int i=0;i<n;i++){
scanf("%s",mat[k][i]);
for(int j=0;j<m;j++)
if(mat[k][i][j]=='P') goal.x = i,goal.y = j,goal.z = k;
}
solve_question();
}
return 0;
}
#include<iostream>
#include<cstring>
#include<cstdio>
#include<queue>
using namespace std;
const int N = 10 + 5;
const int INF = (1<<30);
char mat[2][N][N];
bool visit[2][N][N];
typedef struct node{
int x,y,z,val;
node(int x=0,int y=0,int z=0,int val=0):x(x),y(y),z(z),val(val){}
}Node;
Node goal;
int n,m,k;
const int dir[4][2]={{1,0},{-1,0},{0,1},{0,-1}};
bool BFS(){
queue<Node> Q;
int ans = INF;
Node t,s;
Q.push(Node(0,0,0));
visit[0][0][0] = true;
while(!Q.empty()){
t = Q.front();Q.pop();
if(t.x==goal.x && t.y == goal.y && t.z == goal.z && t.val<=k) { ans=min(ans,t.val);continue;}
for(int d=0;d<4;d++){
int newx = t.x + dir[d][0];
int newy = t.y + dir[d][1];
if(newx >= 0 && newx < n && newy >=0 && newy < m && !visit[t.z][newx][newy] && mat[t.z][newx][newy]!='*'){
if(mat[t.z][newx][newy]=='#' && !visit[t.z^1][newx][newy]){
s.x =newx,s.y= newy ,s.val = t.val+1,s.z = t.z^1;
visit[t.z^1][newx][newy] = visit[t.z][newx][newy] = true;
Q.push(s);
}else{
s.x = newx , s.y = newy,s.val = t.val+1,s.z = t.z;
visit[t.z][newx][newy] = true;
//if(t.val <= k)
Q.push(s);
}
}
}
}
return ans!=INF;
}
void solve_question(){
memset(visit,0,sizeof(visit));
for(int i=0;i<n;i++)
for(int j=0;j<m;j++){
if(mat[0][i][j]=='*' && mat[1][i][j]=='#') mat[0][i][j] = mat[1][i][j] = '*';
if(mat[0][i][j]=='#' && mat[1][i][j]=='*') mat[0][i][j] = mat[1][i][j] = '*';
if(mat[0][i][j]=='#' && mat[1][i][j]=='#') mat[0][i][j] = mat[1][i][j] = '*';
}
printf("%s\n",BFS()?"YES":"NO");
}
int main(){
int T;
scanf("%d",&T);
while(T--){
scanf("%d %d %d",&n,&m,&k);
for(int k=0;k<2;k++)
for(int i=0;i<n;i++){
scanf("%s",mat[k][i]);
for(int j=0;j<m;j++)
if(mat[k][i][j]=='P') goal.x = i,goal.y = j,goal.z = k;
}
solve_question();
}
return 0;
}