Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
双向bfs,为啥会T#include<iostream> #include<queue> #include<stdio.h> using namespace std; char g[35][35][35]; int vis1[35][35][35],vis2[35][35][35]; int l,n,m,dir[6][3]={ 1,0,0, -1,0,0, 0,1,0, 0,-1,0, 0,0,1, 0,0,-1, }; struct place{ int x,y,z,st; place(int xx,int yy,int zz,int ss){ x=xx; y=yy; z=zz; st=ss; } }; bool check1(place cur){ if(g[cur.x][cur.y][cur.z]=='#'||cur.x==0||cur.x==n+1||cur.y==0||cur.z==0||cur.y==m+1||cur.z==l+1||g[cur.x][cur.y][cur.z]=='1')return false; return true; } bool check2(place cur){ if(g[cur.x][cur.y][cur.z]=='#'||cur.x==0||cur.x==n+1||cur.y==0||cur.z==0||cur.y==m+1||cur.z==l+1||g[cur.x][cur.y][cur.z]=='2')return false; return true; } int main(){ while(true){ int f=0; scanf("%d%d%d",&l,&n,&m); if(l==0&&n==0&&m==0)break; queue<place>q,q1; for(int i=1;i<=l;i++){ for(int j=1;j<=n;j++){ for(int k=1;k<=m;k++){ vis1[j][k][i]=0; vis2[j][k][i]=0; char ch=getchar(); while(ch==' '||ch=='\n')ch=getchar(); g[j][k][i]=ch; if(g[j][k][i]=='S'){ place s(j,k,i,0); q.push(s); } if(g[j][k][i]=='E'){ place s(j,k,i,0); q1.push(s); } } } } while(!q.empty()&&!q1.empty()){ if(q.size()<=q1.size()){ place cur=q.front(); int st=cur.st; q.pop(); if(g[cur.x][cur.y][cur.z]=='E'||vis2[cur.x][cur.y][cur.z]){ st+=vis2[cur.x][cur.y][cur.z]; printf("Escaped in %d minute(s).",st); f=1; break; } g[cur.x][cur.y][cur.z]='1'; vis1[cur.x][cur.y][cur.z]=st; for(int i=0;i<6;i++){ place now(cur.x+dir[i][0],cur.y+dir[i][1],cur.z+dir[i][2],st+1); if(check1(now))q.push(now); } } else{ place cur=q1.front(); int st=cur.st; q1.pop(); if(g[cur.x][cur.y][cur.z]=='S'||vis1[cur.x][cur.y][cur.z]){ st+=vis1[cur.x][cur.y][cur.z]; printf("Escaped in %d minute(s).",st); f=1; break; } g[cur.x][cur.y][cur.z]='2'; vis2[cur.x][cur.y][cur.z]=st; for(int i=0;i<6;i++){ place now(cur.x+dir[i][0],cur.y+dir[i][1],cur.z+dir[i][2],st+1); if(check2(now))q1.push(now); } } } if(f==0)printf("Trapped"); } return 0; } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator