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 lzxzy at 2018-08-20 09:20:20 on Problem 3620
#include <cstdio>
using namespace std;
int n,m,k;

struct avoid 
{
	int x,y;
}a[10005];
bool p[105][105];
int dx[4]={0,-1,0,1};
int dy[4]={1,0,-1,0};

void into()
{
	scanf("%d%d%d",&n,&m,&k);
	int x,y;
	for(int i=1;i<=k;i++)
	{
		scanf("%d%d",&a[i].x,&a[i].y);
		p[a[i].x][a[i].y]=1;
	}
}

int js(int x,int y)
{
	int xx,yy,res=0;
	for(int i=0;i<4;i++)
	{
		xx=x+dx[i];yy=y+dy[i];
		if(p[xx][yy])
		{
			p[xx][yy]=0;
			res+=js(xx,yy);
		}
	}
	return res+1;
}

int main()
{
	into();
	int res=0,ans=0;
	for(int i=1;i<=k;i++)
	{
		if(p[a[i].x][a[i].y])
		{
			p[a[i].x][a[i].y]=0;
			res=js(a[i].x,a[i].y);
			if(res>ans)ans=res;
		}
	}
	printf("%d\n",ans);
	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