{{{ #!cplusplus /* zju 1438 hdu 1240 经典:三维BFS ymc 2008/9/16 题目大意: 三维迷宫问题:注意输入是x,y,z的顺序。 解题思路: BFS搜索 */ #include #include #include using namespace std; const int N=11; char graph[N][N][N]; int dist[N][N][N]; int n; int sx,sy,sz,ex,ey,ez; int step[6][3]={{1,0,0},{-1,0,0},{0,1,0},{0,-1,0},{0,0,1},{0,0,-1}}; void BFS() { memset(dist,255,sizeof(dist)); dist[sx][sy][sz]=0; int x,y,z; int x1,y1,z1; queue q; q.push(sx); q.push(sy); q.push(sz); while(!q.empty()) { x=q.front();q.pop(); y=q.front();q.pop(); z=q.front();q.pop(); if(x==ex&&y==ey&&z==ez) return ; for(int i=0;i<6;i++) { x1=x+step[i][0]; y1=y+step[i][1]; z1=z+step[i][2]; if(x1<0||x1>=n||y1<0||y1>=n||z1<0||z1>=n) continue; if(graph[x1][y1][z1]=='X'||dist[x1][y1][z1]>=0) continue; dist[x1][y1][z1]=dist[x][y][z]+1; q.push(x1);q.push(y1);q.push(z1); } } } int main() { string s; while(cin>>s) { cin>>n; for(int z=0;z>graph[x][y][z]; cin>>sx>>sy>>sz>>ex>>ey>>ez; cin>>s; BFS(); if(dist[ex][ey][ez]<0) cout<<"NO ROUTE"<