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 TSERROF at 2012-10-30 23:36:56 on Problem 2251
#include <iostream>
#include <cstring>
#include <queue>
using namespace std;
char map[52][52][52];
int layer,row,col,si,sj,sl,ei,ej,el;
struct mov
{
	int x,y,step,l;
};
int dir[4][2]={{-1,0},{0,1},{1,0},{0,-1}};
void BFS()
{
	queue<mov>M;
	mov temp;
	temp.x=si,temp.y=sj,temp.step=0,temp.l=sl;
	M.push(temp);
	while(!M.empty())
	{
		temp=M.front();
		M.pop();
		if(map[temp.x][temp.y][temp.l]=='E'){ cout<<"Escaped in "<<temp.step<<" minute(s)."<<endl;return;}
		map[temp.x][temp.y][temp.l]='#';
		mov t;
		for(int i=0;i<4;++i)
		{
			t.x=temp.x+dir[i][0],t.y=temp.y+dir[i][1],t.step=temp.step+1,t.l=temp.l;
			if(map[t.x][t.y][t.l]!='#'){ M.push(t);if(map[t.x][t.y][t.l]!='E')map[t.x][t.y][t.l]='#';}
		}	
		if(temp.l-1>=0 && map[temp.x][temp.y][temp.l-1]!='#')
		{
			t.x=temp.x,t.y=temp.y,t.step=temp.step+1,t.l=temp.l-1;
			M.push(t);
			if(map[t.x][t.y][t.l]!='E')map[t.x][t.y][t.l]='#';
		}
		if(temp.l+1<layer && map[temp.x][temp.y][temp.l+1]!='#')
		{
			t.x=temp.x,t.y=temp.y,t.step=temp.step+1,t.l=temp.l+1;
			M.push(t);
			if(map[t.x][t.y][t.l]!='E')map[t.x][t.y][t.l]='#';
		}
	}
	cout<<"Trapped!"<<endl;
}
int main()
{
	while(cin>>layer>>row>>col && (layer || row || col))
	{
		memset(map,'#',sizeof(map));
		for(int k=0;k<layer;++k)
			for(int i=1;i<=row;++i)
				for(int j=1;j<=col;++j)
				{
					cin>>map[i][j][k];
					if(map[i][j][k]=='S')si=i,sj=j,sl=k;
				}
		BFS();
	}
	return 0;
}

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