poj2251(bfs)

kuangbin带你飞搜索专题:poj2251
这是一道三维bfs裸题..二维的最短路径相信大家都很熟悉，此题从二维拓展到三维...用队列模拟bfs，从而解出此题。vis是记录是否经过某点，dis负责记录到某点的最短路径。

#include <iostream>
#include <cstdio>
#include <string.h>
#include <queue>
using namespace std;
int m, n, h;
const int maxn=33;
char s[maxn][maxn][maxn];
int vis[maxn][maxn][maxn];
int dis[maxn][maxn][maxn];
struct node{
  int x, y, z;
  node(int xx, int yy, int zz)
  {
        x=xx;
        y=yy;
        z=zz;
  }
};
int cm[6]={1,0,-1,0,0,0};
int cn[6]={0,1,0,-1,0,0};
int ch[6]={0,0,0,0,1,-1};
node S=node(0, 0, 0), E=node(0, 0, 0);


int bfs()
{
    queue<node>que;
    que.push(S);
    vis[S.x][S.y][S.z]=1;
    while(!que.empty())
    {
        node no=que.front();
        que.pop();
        int x=no.x, y=no.y, z=no.z;
        for(int i=0; i<6; i++)
        {
            int nx=x+cm[i], ny=y+cn[i], nz=z+ch[i];
            if(nx==E.x&&ny==E.y&&nz==E.z)
            {
                return dis[x][y][z]+1;
            }
            if(nx>=0&&nx<m&&ny>=0&&ny<n&&nz>=0&&nz<h&&s[nx][ny][nz]=='.'&&!vis[nx][ny][nz])
            {
                vis[nx][ny][nz]=1;
                que.push(node(nx, ny, nz));
                dis[nx][ny][nz]=dis[x][y][z]+1;
            }
        }
    }
    return -1;
}



int main(void)
{
    while(scanf("%d%d%d", &m, &n, &h)&&m&&n&&h)
    {
        memset(dis, 0, sizeof(dis));
        memset(vis, 0, sizeof(vis));
        for(int i=0; i<m; i++)
        {
            for(int j=0; j<n; j++)
            {
                scanf("%s", s[i][j]);
            }
        }
        for(int i=0; i<m; i++)
        {
            for(int j=0; j<n; j++)
            {
                for(int k=0; k<h; k++)
                {
                    if(s[i][j][k]=='S')
                    S=node(i, j, k);
                    if(s[i][j][k]=='E')
                    E=node(i, j, k);
                }
            }
        }

        int res=bfs();
        if(res==-1)printf("Trapped!\n");
        else printf("Escaped in %d minute(s).\n", res);
    }
    return 0;
}

(ps:好久没敲bfs了，裸敲完ac感觉挺有感觉的～)
over