HDU 1240

 1 #include <iostream>
 2 #include <cstdio>
 3 using namespace std;
 4 
 5 const int MAX=13;
 6 
 7 char maze[MAX][MAX][MAX];
 8 
 9 struct {
10     int i,j,k;
11 }beg,des,que[1100],tmp,pushed;
12 int f,l;
13 char str[15],n;
14 bool vis[MAX][MAX][MAX];
15 int dir[6][3]={1,0,0,-1,0,0,0,1,0,0,-1,0,0,0,1,0,0,-1};
16 
17 bool ok(int i,int j,int k){
18     if(i<0||i>=n||j<0||j>=n||k<0||k>=n||vis[i][j][k]||maze[i][j][k]=='X')
19     return false;
20     return true;
21 }
22 
23 bool bfs(){
24     int step=0; int ti,tj,tk;
25     bool flag=false;
26     while(f<l){
27         int size=l-f;
28         step++;
29         while(size--){
30             tmp=que[f++];
31             if(tmp.i==des.i&&tmp.j==des.j&&tmp.k==des.k){
32                 flag=true;
33                 break;
34             }
35             for(int i=0;i<6;i++){
36                 ti=tmp.i+dir[i][0];
37                 tj=tmp.j+dir[i][1];
38                 tk=tmp.k+dir[i][2];
39                 if(ok(ti,tj,tk)){
40                     vis[ti][tj][tk]=true;
41                     pushed.i=ti; pushed.j=tj; pushed.k=tk;
42                     que[l++]=pushed;
43                 }
44             }
45         }
46         if(flag) break;
47     }
48     if(flag){
49         printf("%d %d
",n,step-1);
50         return true;
51     }
52     return false;
53 }
54 
55 
56 int main(){
57     while(scanf("%s %d",str,&n)!=EOF){
58         for(int i=0;i<n;i++){
59             for(int j=0;j<n;j++)
60             cin>>maze[i][j];
61         }
62     //    cout<<"NO"<<endl;
63         scanf("%d%d%d",&beg.j,&beg.k,&beg.i);
64         scanf("%d%d%d",&des.j,&des.k,&des.i);
65         cin>>str;
66     //    cout<<"YES"<<endl;
67         memset(vis,false,sizeof(vis));
68         f=l=0;
69         if(beg.i==des.i&&beg.j==des.j&&beg.k==des.k){
70             printf("%d 0
",n);
71             continue;
72         }
73         vis[beg.i][beg.j][beg.k]=true;
74         que[l++]=beg;
75         if(!bfs())
76         printf("NO ROUTE
");
77     }
78     return 0;
79 }
View Code