| ||||||||||
| 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 <string.h>
#include <stdio.h>
int maze[100][100][100];
int vis[100][100][100];
int dis[100][100][100];
int q[60000];
int l,r,c;
int flag;
int dx[]={1,-1,0,0,0,0};
int dy[]={0,0,0,0,-1,1};
int dz[]={0,0,-1,1,0,0};
int bfs(int x,int y,int z)
{
int front=0,rear=0,d,u;
vis[x][y][z]=1;
dis[x][y][z]=0;
u=x*r*c+y*c+z;
q[rear++]=u;
while(front<rear)
{
u=q[front++];
x=u/(r*c);
y=(u%(r*c))/c;
z=(u%(r*c))%c;
for(d=0;d<6;d++)
{
int nx=x+dx[d];
int ny=y+dy[d];
int nz=z+dz[d];
if(nx>=0&&nx<l&&ny>=0&&ny<r&&nz>=0&&nz<c&&maze[nx][ny][nz]&&vis[nx][ny][nz]==0)
{
int v=nx*r*c+ny*c+nz;
q[rear++]=v;
vis[nx][ny][nz]=1;
dis[nx][ny][nz]=dis[x][y][z]+1;
if(maze[nx][ny][nz]==2)
{
return dis[nx][ny][nz];
}
}
}
}
return 0;
}
int main()
{
int i,j,k;
char s[100];
int a1,b1,c1;
int time;
while(scanf("%d %d %d",&l,&r,&c)==3&&l!=0&&r!=0&&c!=0)
{
getchar();
flag=1;
memset(maze,0,sizeof(maze));
memset(vis,0,sizeof(vis));
for(i=0;i<l;i++)
{
for(j=0;j<r;j++)
{
gets(s);
for(k=0;k<c;k++)
{
if(s[k]=='S')
{
a1=i;
b1=j;
c1=k;
}
else if(s[k]=='.')
{
maze[i][j][k]=1;
}
else if(s[k]=='E')
{
maze[i][j][k]=2;
}
}
}
getchar();
}
time=bfs(a1,b1,c1);
if(time)
{
printf("Escaped in %d minute(s).\n",time);
}
else
{
printf("Trapped!\n");
}
}
}
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator