在做了两道BFS题目以后，细细琢磨，我很欣慰我理解了一些BFS 的快速敲写套路...
POJ 2251 ：http://poj.org/problem?id=2251
题意： 立方体的迷宫，走出迷宫的最少步数。
起点S终点E，障碍' # ' ，通路为 ' . '
就是三维的BFS。套路一模一样。
完好的BFS套路，采取的是我的 基础搜索 BFS 三里面的思想：
队列里放的都是当前标记好了的。
取一个点，对周遭拓展 未出界并且未标记的点，标记并入队。
清晰明了。
BFS代码：
#include"cstdio" #include"queue" #include"cstring" #include"algorithm" #include"queue" using namespace std; #define inf 999999999 #define loop(x,y,z) for(x=y;x<z;x++) int sx,sy,sz; int gx,gy,gz; int n,m,k,ans; char map[31][31][31]; int pos[6][3]={0,0,1,0,0,-1,1,0,0,-1,0,0,0,1,0,0,-1,0}; struct node{ int x,y,z,step; node(int i,int j,int o,int t) { x=i;y=j;z=o;step=t; } }; queue<node>q; int pan(int i,int j,int o) { if(i<0||j<0||o<0||i>=n||j>=m||o>=k)return 0; return 1; } void bfs() { node t(sx,sy,sz,0); q.push(t); map[sx][sy][sz]='#'; while(!q.empty()) { node t=q.front(); q.pop(); for(int i=0;i<6;i++) { int x=t.x+pos[i][0]; int y=t.y+pos[i][1]; int z=t.z+pos[i][2]; if(!pan(x,y,z))continue; if(map[x][y][z]!='#') { map[x][y][z]='#'; q.push(node(x,y,z,t.step+1)); if(map[gx][gy][gz]=='#'){ans=t.step+1;return;} } } } } int main() { int i,j,o; while(~scanf("%d%d%d",&n,&m,&k)) { if(n==0&&m==0&&k==0)break; while(!q.empty())q.pop(); ans=inf; loop(i,0,n) loop(j,0,m) scanf("%s",map[i][j]); loop(i,0,n) loop(j,0,m) loop(o,0,k) if(map[i][j][o]=='S') { sx=i;sy=j;sz=o; } else if(map[i][j][o]=='E') { gx=i;gy=j;gz=o; } bfs(); if(ans!=inf) printf("Escaped in %d minute(s).\n",ans); else printf("Trapped!\n"); } return 0; }
