hdu1240 bfs 水題

原題鏈接

思路：水題，直接搜

 1 #include "map"
 2 #include "queue"
 3 #include "math.h"
 4 #include "stdio.h"
 5 #include "string.h"
 6 #include "iostream"
 7 #include "algorithm"
 8 #define abs(x) x > 0 ? x : -x
 9 #define max(a,b) a > b ? a : b
10 #define min(a,b) a < b ? a : b
11 
12 using namespace std;
13 
14 int z2,x2,y2,n;
15 int d[6][3]= {{0,0,1},{0,1,0},{0,0,-1},{0,-1,0},{1,0,0},{-1,0,0}};
16 bool Map[15][15][15],vis[15][15][15];
17 
18 struct Node{
19     int zz,xx,yy;
20     int step;
21 };
22 
23 void Bfs(int z,int x,int y)
24 {
25     memset(vis,0,sizeof(vis));
26     queue<Node>Q;
27     Node now,next;
28 
29     now.zz = z;
30     now.xx = x;
31     now.yy = y;
32     now.step = 0;
33     vis[z][x][y] = 1;
34 
35     Q.push(now);
36 
37     while(!Q.empty())
38     {
39         now = Q.front();
40         Q.pop();
41 
42         if(now.zz==z2 && now.xx==x2 && now.yy==y2)
43         {
44             printf("%d %d\n",n,now.step);
45             return;
46         }
47 
48         for(int i=0; i<6; i++)
49         {
50             next.zz = now.zz + d[i][0];
51             next.xx = now.xx + d[i][1];
52             next.yy = now.yy + d[i][2];
53             next.step = now.step + 1;
54 
55             if(Map[next.zz][next.xx][next.yy] && !vis[next.zz][next.xx][next.yy])
56             {
57                 vis[next.zz][next.xx][next.yy] = 1;
58                 Q.push(next);
59             }
60         }
61     }
62     printf("NO ROUTE\n");
63 }
64 
65 int main()
66 {
67     int x1,y1,z1,i,j,k;
68     char s[20],c;
69     while(~scanf("%s%d",s,&n))
70     {
71         memset(Map,0,sizeof(Map));
72         for(i=1; i<=n; i++)
73             for(j=1; j<=n; j++)
74             {
75                 getchar();
76                 for(k=1; k<=n; k++)
77                 {
78                     scanf("%c",&c);
79                     if(c=='O')
80                         Map[i][j][k] = 1;
81                     if(c=='X')
82                         Map[i][j][k] = 0;
83                 }
84             }
85 
86         scanf("%d%d%d%d%d%d",&x1,&y1,&z1,&x2,&y2,&z2);
87         z1+=1,x1+=1,y1+=1,z2+=1,x2+=1,y2+=1;
88         getchar();
89         gets(s);
90 
91         Bfs(z1,x1,y1);
92     }
93     return 0;
94 }