POJ2251——BFS三維迷宮

初學廣搜算法可以看 http://blog.csdn.net/chuck001002004/article/details/50404122

POJ2251：http://poj.org/problem?id=2251

題意：輸入l，r，c 三個數，代表一個 l 層的 r * c 大小的迷宮，S表示起點，E表示終點，‘ . ’表示可以走，‘#’表示走不了，求從起點到終點的最少步數，若走不出則輸出“Trapped！”

分析：是不是被吓住了！！！其實就是比二維的迷宮多了上下兩個點而已，寫入BFS算法就是了。

代碼：

#include <iostream>
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <math.h>
#include <queue>
using namespace std;
char a[35][35][35];
int vis[35][35][35],l,r,c;
int si,sj,sk,ei,ej,ek;//起點和終點對應的坐标
int dl[]={-1,1};      //變動上下
int dr[]={1,0,-1,0};  //變動左右
int dc[]={0,1,0,-1};  //變動前後

struct node
{
    int l,r,c,sum; //定義點h尤其對應的層數，橫縱坐标和步數值
}h;
queue <node> que;  //建立隊列
int BFS()
{
    //算法開始前清空隊列
    while(!que.empty())
        que.pop();
    //将開始點的坐标賦給h
    h.l=si;h.r=sj;h.c=sk;
    h.sum=0;    //初始步數為0
    que.push(h);//将h放入隊列
    vis[h.l][h.r][h.c]=1; //切記标記通路
    //定義目前點和可到達的點
    node cur,next;
    while(!que.empty())
    {
        cur=que.front();
        que.pop();
        //如果目前點為出口，傳回其步數值
        if(cur.l==ei&&cur.r==ej&&cur.c==ek) 
            return cur.sum;
        //若不是，檢視其上下的點
        for(int i=0;i<2;i++)
        {
            //上下可到達點的坐标和步數
            next.l=cur.l+dl[i];
            next.r=cur.r;
            next.c=cur.c;
            next.sum=cur.sum+1;
            //點在範圍内且未被通路且可走
            if(next.l>=1&&next.l<=l&&a[next.l][next.r][next.c]!='#'&&!vis[next.l][next.r][next.c])
            {
                que.push(next);   //加入隊尾
                vis[next.l][next.r][next.c]=1; //标記通路
            }
        }
        //再看前後左右四點，方法大緻同上
        for(int i=0;i<4;i++)
        {
            next.l=cur.l;
            next.r=cur.r+dr[i];
            next.c=cur.c+dc[i];
            next.sum=cur.sum+1;
            if(next.r>0&&next.r<=r&&next.c>0&&next.c<=c)
            {
                if(a[next.l][next.r][next.c]!='#'&&!vis[next.l][next.r][next.c])
                {
                    que.push(next);
                    vis[next.l][next.r][next.c]=1;
                }
            }
        }
    }
    return 0; //走不出去就傳回0
}

int main()
{
    while(cin>>l>>r>>c)
    {
        if(!l&&!r&&!c) break;
        memset(a,0,sizeof(a));
        for(int i=1;i<=l;i++)
        {
            for(int j=1;j<=r;j++)
            {
                for(int k=1;k<=c;k++)
                {
                    //輸入的同時記錄起點終點坐标
                    cin>>a[i][j][k];
                    if(a[i][j][k]=='S') {si=i;sj=j;sk=k;}
                    if(a[i][j][k]=='E') {ei=i;ej=j;ek=k;}
                }
            }
        }
        memset(vis,0,sizeof(vis));
        int sum=BFS();
        if(sum) cout<<"Escaped in "<<sum<<" minute(s)."<<endl;
        else cout<<"Trapped!"<<endl;
    }
    return 0;
}
           

網上有說這題用DFS，别信！！！