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

dfs怎么过不了

Posted by dynamic_study at 2009-08-08 21:10:20 on Problem 1652
#include<iostream>
using namespace std;
int n,m,ans,sum,MAX;
int dir[4][2]={{-1,0},{0,1},{1,0},{0,-1}};

char map[122][122];
void  dfs(int sx,int sy)
{
//	cout<<sx<<" "<<sy<<" "<<sum<<endl;
	if(sum<MAX)
		return;
	int i;
	ans++;
	if(sx<1||sx>n||sy<1||sy>m)
	   return;
	for(i=0;i<4;i++)
	{
		if(sx+dir[i][0]<=n&&sx+dir[i][0]>=1&&
sy+dir[i][1]>=1&&sy+dir[i][1]<=m&&map[sx+dir[i][0]][sy+dir[i][1]]=='*')
		{   
			map[sx+dir[i][0]][sy+dir[i][1]]='.';
			dfs(sx+dir[i][0],sy+dir[i][1]);
		//	map[sx+dir[i][0]][sy+dir[i][1]]='*';
		}
	}
}
int main()
{
	int i,j;
    while(cin>>m>>n)
	{
	if(m==0&&n==0)
		break;
	sum=0;
	for(i=1;i<=n;i++)
		for(j=1;j<=m;j++)
		{
			cin>>map[i][j];
			if(map[i][j]=='*')
				sum++;
		}
		MAX=0;
	for(i=1;i<=n;i++)
		for(j=1;j<=m;j++)
		{
			if(map[i][j]=='*')
			{  	ans=0;
			    map[i][j]='.';
                dfs(i,j);
				if(ans>MAX)
					MAX=ans;
				sum-=ans;
			}
		}
		cout<<MAX<<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