Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

比较清晰了 三维BFS

Posted by 201101050424 at 2012-01-20 11:22:55 on Problem 2251
#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:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator