題目鏈接：http://poj.org/PRoblem?id=2251 題意：給你一個三維迷宮，S是起點，E是終點，#不可走 解析：直接開個三維數組，BFS就好
#include <algorithm>#include <cstring>#include <cstdio>#include <queue>using namespace std;const int inf = 0x7fffffff;int L,R,C;int vis[50][50][50];char mapple[50][50][50];int ans;int dx[] = {0,1,-1,0,0,0};int dy[] = {1,0,0,-1,0,0};int dz[] = {0,0,0,0,1,-1};int sx,sy,sz;struct node{ int x,y,z; int step; node() {} node(int _x,int _y,int _z,int _step) { x = _x; y = _y; z = _z; step = _step; }};int bfs(){ ans = inf; memset(vis,0,sizeof(vis)); queue<node> q; q.push(node(sx,sy,sz,0)); vis[sx][sy][sz] = 1; while(!q.empty()) { node now = q.front(); q.pop(); if(mapple[now.x][now.y][now.z]=='E') return now.step; for(int i=0;i<6;i++) { int tx = now.x+dx[i]; int ty = now.y+dy[i]; int tz = now.z+dz[i]; if(tx<0||tx>=L || ty<0||ty>=R || tz<0 || tz>=C) continue; if(mapple[tx][ty][tz]=='#' || vis[tx][ty][tz]) continue; vis[tx][ty][tz] = 1; q.push(node(tx,ty,tz,now.step+1)); } } return inf;}int main(void){ while(~scanf("%d %d %d",&L,&R,&C)) { if(L==0&&R==0&&C==0) break; for(int i=0;i<L;i++) { for(int j=0;j<R;j++) { scanf("%s",mapple[i][j]); for(int k=0;k<C;k++) { if(mapple[i][j][k]=='S') { sx = i; sy = j; sz = k; } } } } ans = bfs(); if(ans==inf) puts("Trapped!"); else printf("Escaped in %d minute(s)./n",ans); } return 0;}新聞熱點
疑難解答
