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 |
水过//6方向搜索 #include <iostream> #include<cstdio> #include<queue> #include<cstring> using namespace std; const int maxn=30+5; int dx[]={-1,1,0,0,0,0}; int dy[]={0,0,-1,1,0,0}; int dz[]={0,0,0,0,-1,1}; int l,r,c; //层数 行数 列数 char field[maxn][maxn][maxn]; int d[maxn][maxn][maxn]; int sx,sy,sz; int gx,gy,gz; struct point{ int x,y,z; point(int x,int y,int z):x(x),y(y),z(z) {} }; void bfs() { memset(d,-1,sizeof(d)); d[sx][sy][sz]=0; queue<point>pq; pq.push(point(sx,sy,sz)); while(!pq.empty()) { point ss=pq.front(); pq.pop(); if(ss.x==gx&&ss.y==gy&&ss.z==gz) return; for(int i=0;i<6;i++) { int nx=ss.x+dx[i],ny=ss.y+dy[i],nz=ss.z+dz[i]; if(nx>=0&&nx<l&&ny>=0&&ny<r&&nz>=0&&nz<c&&field[nx][ny][nz]!='#'&&d[nx][ny][nz]==-1) { pq.push(point(nx,ny,nz)); d[nx][ny][nz]=d[ss.x][ss.y][ss.z]+1; } } } } int main() { while(scanf("%d%d%d",&l,&r,&c)==3) { if(!l&&!r&&!c) break; for(int i=0;i<l;i++) for(int j=0;j<r;j++) { scanf("%s",&field[i][j]); //i层 j行 for(int k=0;k<c;k++) { if(field[i][j][k]=='S') { sx=i; sy=j; sz=k; } if(field[i][j][k]=='E') { gx=i; gy=j; gz=k; } } } bfs(); if(d[gx][gy][gz]==-1) printf("Trapped!\n"); else printf("Escaped in %d minute(s).\n",d[gx][gy][gz]); } return 0; } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator