```   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 }
```

hdu1240 参考答案 (last edited 2008-09-19 16:44:41 by 218)

ch3n2k.com | Copyright (c) 2004-2020 czk.