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

C++福利

Posted by 1908847416 at 2015-12-03 13:08:15 on Problem 2446
#include<cstdio>
#include<cstdlib>
#include<cstring>
using namespace std;

int ans;
int n,m,kk;
int a[1030];
bool sss[1030];
int aa[1030][1030];
bool tf[1030][1030];
bool ttf[1030][1030];

bool found(int x)
{
	for(int i=1;i<=n*m;i++)
	{
		if(tf[x][i]==true && sss[i]==true)
		{
			sss[i]=false;
			if(a[i]==0 || found(a[i])==true)
			{
				a[i]=x;
				return true;
			}
		}
	}
	return false;
}

int main()
{
	while(scanf("%d %d %d",&n,&m,&kk)!=EOF)
	{
		if((n*m-kk)%2!=0)
		{
			printf("NO\n");
			continue;
		}	
		int num=0;
		for(int i=1;i<=n;i++)
		{
			for(int j=1;j<=m;j++)
			{
				num++;
				aa[i][j]=num;
			}
		}
		int x,y;
		memset(tf,false,sizeof(tf));
		memset(ttf,true,sizeof(ttf));
		for(int i=1;i<=kk;i++)
		{
			scanf("%d %d",&x,&y); 
			ttf[y][x]=false;
		}
		for(int i=1;i<=n;i++)
		{
			for(int j=1;j<=m;j++)
			{
				if(ttf[i][j]==false)	continue;
				tf[aa[i][j]][aa[i-1][j]]=ttf[i-1][j];
				tf[aa[i][j]][aa[i][j-1]]=ttf[i][j-1];
				tf[aa[i][j]][aa[i][j+1]]=ttf[i][j+1];
				tf[aa[i][j]][aa[i+1][j]]=ttf[i+1][j];
			}
		}
		ans=0;
		memset(a,0,sizeof(a));
		for(int i=1;i<=n;i++)
		{
			for(int j=1;j<=m;j++)
			{
				memset(sss,true,sizeof(sss));
				if(found(aa[i][j])==true)	ans++;	
			}
		}
		ans/=2;
		if(ans == (n*m-kk)/2)	printf("YES\n");
		else	printf("NO\n");	
		}
} 

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