首页 > 代码库 > HDU 1240

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",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",n);71             continue;72         }73         vis[beg.i][beg.j][beg.k]=true;74         que[l++]=beg;75         if(!bfs())76         printf("NO ROUTE\n");77     }78     return 0;79 }
View Code