Input
Output
Escaped in x minute(s).
Trapped!
Sample Input
3 4 5 S.... .###. .##.. ###.# ##### ##### ##.## ##... ##### ##### #.### ####E 1 3 3 S## #E# ### 0 0 0
Sample Output
Escaped in 11 minute(s). Trapped!
就是六个方向的广搜,理清楚就好做
#include<iostream>
#include<cstring>
#include<queue>
using namespace std;
int a,b,c;
char s[30][30][30];
int map[30][30][30];
int next[6][3] = {{0,0,1},{0,0,-1},{0,1,0},{0,-1,0},{1,0,0},{-1,0,0}};
int si,sj,sk,ei,ej,ek;
struct node
{
int x,y,z;
int step;
};
int check(int x,int y,int z)
{
if(x<0 || y<0 || z<0 || x>=a || y>=b || z>=c)
return 1;
else if(s[x][y][z] == ‘#‘)
return 1;
else if(map[x][y][z])
return 1;
return 0;
}
int bfs()
{
queue <node> q;
node t,no;
t.x=si;t.y=sj;t.z=sk;
t.step=0;
map[si][sj][sk]=1;
q.push(t);
while(!q.empty())
{
t=q.front();
q.pop();
if(t.x == ei && t.y == ej && t.z == ek)
return t.step;
for(int i = 0; i<6; i++)
{
no = t;
no.x = t.x+next[i][0];
no.y = t.y+next[i][1];
no.z = t.z+next[i][2];
if(check(no.x,no.y,no.z))
continue;
map[no.x][no.y][no.z] = 1;
no.step = t.step+1;
q.push(no);
}
}
return 0;
}
int main()
{
while(cin>>a>>b>>c)
{
if(a==0&&b==0&&c==0)
break;
for(int i=0;i<a;i++)
{
for(int j=0;j<b;j++)
{
for(int k=0;k<c;k++)
{
cin>>s[i][j][k];
if(s[i][j][k]==‘S‘)
{
si=i;
sj=j;
sk=k;
}
if(s[i][j][k]==‘E‘)
{
ei=i;
ej=j;
ek=k;
}
}
}
}
memset(map,0,sizeof(map));
int ans=bfs();
if(ans)
cout<<"Escaped in "<<ans<<" minute(s)."<<endl;
else
cout<<"Trapped!"<<endl;
}
return 0;
}
原文:http://www.cnblogs.com/zzzying/p/7236505.html