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 lbbde at 2010-07-24 17:02:40 on Problem 2312
A的艰难啊
#include<iostream>
#include<queue>
using namespace std;

char map[400][400];
int m,n;
int x1,y1;
int x2,y2;
int move[4][2]={{-1,0},{1,0},{0,-1},{0,1}};
bool visit[400][400];

struct note
{
	int x;
	int y;
	int turn;
	
};

void bfs()
{
	
	queue<note> q;
	int front=0,rear=0;
	note current,next;
	current.x=x1;
	current.y=y1;
	current.turn=0;
    q.push(current);
	visit[x1][y1]=true;
	
	
	int i;
	bool p=false;
	while(!q.empty())
	{
		current=q.front();
		q.pop();
		if(current.x==x2&&current.y==y2)   {p=true;break;}
		
		if(map[current.x][current.y]=='B')
		{
			current.turn++;
			q.push(current);
			map[current.x][current.y]='E';
		}
		else 
		{
		for(i=0;i<4;i++)
		{
			next.x=current.x+move[i][0];
			next.y=current.y+move[i][1];
			if(next.x>=0&&next.x<m&&next.y>=0&&next.y<n&&!visit[next.x][next.y]&&map[next.x][next.y]!='S'&&map[next.x][next.y]!='R')
			{
					next.turn=current.turn+1;
					q.push(next);
					visit[next.x][next.y]=true;
				}
			}
		}
		}

	if(!p)  printf("-1\n");
	else  printf("%d\n",current.turn);
}


int main()
{
	while(scanf("%d%d",&m,&n)!=EOF)
	{
		memset(visit,false,sizeof(visit));
		if(m==0&&n==0)  break;
		int i,j;
		for(i=0;i<m;i++)
			for(j=0;j<n;j++)
			{
				cin>>map[i][j];
				if(map[i][j]=='Y')
				{
					x1=i;
					y1=j;
				}
				else if(map[i][j]=='T')
				{
					x2=i;
					y2=j;
				}
			}
			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