hdu1240 参考答案

   1 /*
   2 zju 1438  hdu 1240 经典：三维BFS
   3 ymc 2008/9/16
   4 题目大意：
   5 三维迷宫问题:注意输入是x，y，z的顺序。
   6 解题思路：
   7 BFS搜索
   8 */
   9 #include <iostream>
  10 #include <string>
  11 #include <queue>
  12 using namespace std;
  13 const int N=11;
  14 char graph[N][N][N];
  15 int dist[N][N][N];
  16 int n;
  17 int sx,sy,sz,ex,ey,ez;
  18 int step[6][3]={{1,0,0},{-1,0,0},{0,1,0},{0,-1,0},{0,0,1},{0,0,-1}};
  19 void BFS()
  20 {
  21         memset(dist,255,sizeof(dist));
  22         dist[sx][sy][sz]=0;
  23         int x,y,z;
  24         int x1,y1,z1;
  25         queue<int> q;
  26         q.push(sx);     q.push(sy);     q.push(sz);
  27         while(!q.empty())
  28         {
  29                 x=q.front();q.pop();
  30                 y=q.front();q.pop();
  31                 z=q.front();q.pop();
  32                 if(x==ex&&y==ey&&z==ez)
  33                         return ;
  34                 for(int i=0;i<6;i++)
  35                 {
  36             x1=x+step[i][0];
  37             y1=y+step[i][1];
  38             z1=z+step[i][2];
  39             if(x1<0||x1>=n||y1<0||y1>=n||z1<0||z1>=n)
  40                 continue;
  41             if(graph[x1][y1][z1]=='X'||dist[x1][y1][z1]>=0)
  42                 continue;
  43             dist[x1][y1][z1]=dist[x][y][z]+1;
  44             q.push(x1);q.push(y1);q.push(z1);
  45         }
  46         }
  47 }
  48 int main()
  49 {
  50         string s;
  51         while(cin>>s)
  52         {
  53                 cin>>n;
  54                 for(int z=0;z<n;z++)
  55                         for(int y=0;y<n;y++)
  56                                 for(int x=0;x<n;x++)
  57                                         cin>>graph[x][y][z];
  58                 cin>>sx>>sy>>sz>>ex>>ey>>ez;
  59                 cin>>s;
  60                 BFS();
  61                 if(dist[ex][ey][ez]<0)
  62                         cout<<"NO ROUTE"<<endl;
  63                 else
  64                         cout<<n<<' '<<dist[ex][ey][ez]<<endl;
  65         }
  66 }