学步园

给定一个3D迷宫判断走出去的最小步数....

Sample Input

3 4 5
S....
.###.
.##..
###.#

#####
#####
##.##
##...

#####
#####
#.###
####E

1 3 3
S##
#E#
###

0 0 0

Sample Output

Escaped in 11 minute(s).
Trapped!

我的首个BFS题，感谢小杰的教导，谢谢他。。。！

解题思路：刚开始用深搜超时了，怎么优化都不行，后来才知道这个得用宽搜，哎菜啊。 学习了。。

BFS的代码

#include<iostream><br /> using namespace std;<br /> struct mov<br /> {<br /> int x,y,z;<br /> }mov[6]={1,0,0,-1,0,0,0,1,0,0,-1,0,0,0,1,0,0,-1};<br /> char map[35][35][35],lock[35][35][35]; int L,R,C;</p> <p>int queue[1000000],head,rear;</p> <p>int pop(){ return queue[head++%1000000]; }<br /> void push(int i) { queue[rear++%1000000]=i; }<br /> int bfs(int i,int j,int k)<br /> {<br /> int num,x,y,z,fang;<br /> while(head!=rear)<br /> {<br /> x=pop(); y=pop(); z=pop(); num=pop();<br /> for(fang=0;fang<6;fang++)<br /> if(x+mov[fang].x>-1&&x+mov[fang].x<L&&y+mov[fang].y>-1&&y+mov[fang].y<R&&z+mov[fang].z>-1&&z+mov[fang].z<C&&lock[x+mov[fang].x][y+mov[fang].y][z+mov[fang].z]==0&&(map[x+mov[fang].x][y+mov[fang].y][z+mov[fang].z]=='.'||map[x+mov[fang].x][y+mov[fang].y][z+mov[fang].z]=='E'))<br /> {<br /> if(map[x+mov[fang].x][y+mov[fang].y][z+mov[fang].z]=='E')<br /> return num+1;<br /> lock[x+mov[fang].x][y+mov[fang].y][z+mov[fang].z]=1;<br /> push(x+mov[fang].x);<br /> push(y+mov[fang].y);<br /> push(z+mov[fang].z);<br /> push(num+1);<br /> }<br /> }<br /> return 0;<br /> }</p> <p>int main()<br /> {<br /> while(cin>>L>>R>>C&&L)<br /> {<br /> head=rear=0;<br /> memset(lock,0,sizeof(lock));<br /> int i,j,o,k;<br /> for(i=0;i<L;i++)<br /> for(j=0;j<R;j++)<br /> scanf("%s",map[i][j]);<br /> for(i=0;i<L;i++)<br /> for(j=0;j<R;j++)<br /> for(k=0;k<C;k++)<br /> if(map[i][j][k]=='S')<br /> goto start;<br /> start: push(i); push(j); push(k); push(0);<br /> o=bfs(i,j,k);<br /> if(o) cout<<"Escaped in "<<o<<" minute(s)."<<endl;<br /> else cout<<"Trapped!"<<endl;</p> <p> }<br /> return 0;<br /> }<br />

DFS超时的

#include<iostream><br /> using namespace std;<br /> struct mov<br /> {<br /> int x,y,z;<br /> }mov[6]={1,0,0,-1,0,0,0,1,0,0,-1,0,0,0,1,0,0,-1};<br /> char map[35][35][35],way[35][35][35]; int L,R,C,minp;</p> <p>int find(int i,int j,int k,int path)<br /> {<br /> if(path>=minp)<br /> return 1;<br /> if(map[i][j][k]=='E')<br /> {<br /> if(path<minp)<br /> minp=path;<br /> return 1;<br /> }<br /> int fang,flag=0;<br /> for(fang=0;fang<6;fang++)<br /> {<br /> if(i+mov[fang].x>-1&&i+mov[fang].x<L&&j+mov[fang].y>-1&&j+mov[fang].y<R&&k+mov[fang].z>-1&&k+mov[fang].z<C&&way[i+mov[fang].x][j+mov[fang].y][k+mov[fang].z]==0&&(map[i+mov[fang].x][j+mov[fang].y][k+mov[fang].z]=='.'||map[i+mov[fang].x][j+mov[fang].y][k+mov[fang].z]=='E'))<br /> {<br /> way[i+mov[fang].x][j+mov[fang].y][k+mov[fang].z]=1;</p> <p> if(find(i+mov[fang].x,j+mov[fang].y,k+mov[fang].z,path+1))<br /> { way[i+mov[fang].x][j+mov[fang].y][k+mov[fang].z]=0; flag=1; }<br /> }<br /> }<br /> return flag;<br /> }</p> <p>int main()<br /> {<br /> int i,j,k,fang;<br /> while(cin>>L>>R>>C&&(L||R||C))<br /> {<br /> minp=1000000;<br /> memset(way,0,sizeof(way));<br /> for(i=0;i<L;i++)<br /> for(j=0;j<R;j++)<br /> scanf("%s",map[i][j]);<br /> for(i=0;i<L;i++)<br /> for(j=0;j<R;j++)<br /> for(k=0;k<C;k++)<br /> if(map[i][j][k]=='S')<br /> goto start;<br /> start:<br /> for(fang=0;fang<6;fang++)<br /> {<br /> if(i+mov[fang].x>-1&&i+mov[fang].x<L&&j+mov[fang].y>-1&&j+mov[fang].y<R&&k+mov[fang].z>-1&&k+mov[fang].z<C&&way[i+mov[fang].x][j+mov[fang].y][k+mov[fang].z]==0&&(map[i+mov[fang].x][j+mov[fang].y][k+mov[fang].z]=='.'||map[i+mov[fang].x][j+mov[fang].y][k+mov[fang].z]=='E'))<br /> {<br /> way[i+mov[fang].x][j+mov[fang].y][k+mov[fang].z]=1;<br /> if(find(i+mov[fang].x,j+mov[fang].y,k+mov[fang].z,0))<br /> way[i+mov[fang].x][j+mov[fang].y][k+mov[fang].z]=0;<br /> }<br /> }<br /> if(minp>=1000000)<br /> cout<<"Trapped!"<<endl;<br /> else<br /> cout<<"Escaped in "<<minp+1<<" minute(s)."<<endl;<br /> }</p> <p> return 0;<br /> }