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做的 但为什么总wa???希望大牛看看。谢谢

Posted by sunzuhan at 2010-09-06 21:28:32 on Problem 2688
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;

struct node{
	int x;
	int y;
	int step;
}d[250*250];

char map[21][21];

bool used[21][21];

int n,m;
int tot;
int cnt;
int ans=0;

int dir[4][2]={{1,0},{-1,0},{0,1},{0,-1}};

void bfs()
{
	queue <node> q;
	int i,j;
	memset(used,0,sizeof(used));
	
	q.push(d[cnt-1]);
	used[d[cnt-1].x][d[cnt-1].y]=true;
	while(!q.empty())
	{
		node fromv=q.front();
		q.pop();
			for(i=0;i<4;i++)
			{
				node t;
				t.x=fromv.x+dir[i][0];
				t.y=fromv.y+dir[i][1];
				t.step=fromv.step+1;
				
				if(t.x>=0 && t.x<n && t.y>=0 && t.y<m &&
				!used[t.x][t.y] && map[t.x][t.y]!='x')
				{
					if(map[t.x][t.y]=='*')
					{
						tot--;
						ans+=t.step;
						map[t.x][t.y]='.';
						d[cnt].x=t.x;
						d[cnt].y=t.y;
						d[cnt++].step=0;
						return;
					}
					used[t.x][t.y]=true;
					q.push(t);
				}
			}
	}
}		
int main()
{	
	while(cin>>m>>n && (m+n))
	{
		
		int i,j;
		cin.ignore();
		tot=0;
		cnt=0;
		ans=0;
		for(i=0;i<n;i++)
		{
			cin.getline(map[i],25);
			for(j=0;j<m;j++)
			{
				if(map[i][j]=='*')
				tot++;
				
				else if(map[i][j]=='o')
				{
					d[cnt].x=i;
					d[cnt].y=j;
					d[cnt++].step=0;
				}
			}
		}
		
		int num=tot;
		if(!tot)
			cout<<0<<endl;
		else 
		{
			for(i=0;i<num;i++)
				bfs();
			
				if(tot)
			 	cout<<"-1"<<endl;
			 	else 
			 	cout<<ans<<endl;
		}
	}
	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