| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
BFS一次就过,附拙劣代码#include<stdio.h>
#include<string.h>
#include<queue>
using namespace std;
int vis[31][31][31];
char Map[31][31][31];
int step[35][35][35];
int l,r,c;
int dir[6][3]={1,0,0, -1,0,0, 0,1,0, 0,-1,0, 0,0,1, 0,0,-1};
struct point
{
int x,y,z;
} in,out,beg;
int check(int x, int y, int z)
{
if(!vis[z][x][y]&&z >= 0&&z < l&&x >= 0&&x < r&&y >= 0&&y < c&&Map[z][x][y]!='#')
return 1;
return 0;
}
int bfs()
{
memset(vis, 0, sizeof(vis));
memset(step, 0, sizeof(step));
vis[beg.z][beg.x][beg.y] = 1;
step[beg.z][beg.x][beg.y] = 0;
queue<point>q;
q.push(beg);
while(!q.empty())
{
out = q.front();
q.pop();
for(int i = 0; i < 6; ++i)
{
in.z = out.z+dir[i][0];
in.x = out.x+dir[i][1];
in.y = out.y+dir[i][2];
if(check(in.x, in.y, in.z))
{
if(Map[in.z][in.x][in.y]=='E')
return step[out.z][out.x][out.y]+1;
q.push(in);
vis[in.z][in.x][in.y] = 1;
step[in.z][in.x][in.y] = step[out.z][out.x][out.y] + 1;
}
}
}
return -1;
}
int main()
{
while(~scanf("%d%d%d", &l,&r,&c))
{
if(!l&&!r&&!c)break;
for(int i = 0; i < l; ++i)
for(int j = 0; j < r; ++j)
scanf("%s", Map[i][j]);
for(int i = 0; i < l; ++i)
for(int j = 0; j < r; ++j)
for(int k = 0; k < c; ++k)
if(Map[i][j][k]=='S')
{
beg.z = i;
beg.x = j;
beg.y = k;
}
int ans = bfs();
ans==-1?printf("Trapped!\n"):printf("Escaped in %d minute(s).\n", ans);
}
return 0;
}
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator