初学广搜算法可以看 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,别信!!!