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

我找了很多的测试数据,都过了,可提交总是wa,哪位大牛帮我找找错呀,感激不尽。。。 一些测试数据

Posted by shennong at 2012-09-11 17:44:18 on Problem 2446
#include<stdio.h>
#include<string.h>
struct node
{
	int index;
	int color;
}map[35][35];
int borad[520][520],vist[520],pipei[520],count0,count1,m,n;
int dian(int i,int j)
{
	if(i>=1&&i<=m&&j>=1&&j<=n)
	{
		return 1;
	}
	else
	{
		return 0;
	}
}
int dfs(int u)
{
	int v;
	for(v=0;v<count1;v++)
	{
		if(vist[v]==0&&borad[u][v]>0)
		{
			vist[v]=1;
			if(pipei[v]==-1||dfs(pipei[v]))
			{
				pipei[v]=u;
				return 1;
			}
		}
	}
	return 0;
}
int main()
{
	int i,j,k,ans,x,y;
	for(;scanf("%d%d%d",&m,&n,&k)!=EOF;)
	{

		for(i=1;i<=m;i++)
		{
			for(j=1;j<=n;j++)
			{
				map[i][j].color=-1;
				map[i][j].index=0;
			}
		}
		for(i=1;i<=k;i++)
		{
			scanf("%d%d",&x,&y);
			map[y][x].color=2;
		}
		count0=0;
		count1=0;
		for(i=1;i<=m;i++)
		{
			for(j=1;j<=n;j++)
			{
				if((i+j)%2==1&&map[i][j].color!=2)
				{
					map[i][j].color=1;
					map[i][j].index=count1;
					count1++;
				}
				if((i+j)%2==0&&map[i][j].color!=2)
				{
					map[i][j].color=0;
					map[i][j].index=count0;
					count0++;
				}
			}
		}
		/*printf("%d %d\n",count0,count1);
		for(i=1;i<=m;i++)
		{
		for(j=1;j<=n;j++)
		{
		printf("-%d %d-  ",map[i][j].color,map[i][j].index);
		}
		printf("\n");
	}*/
		if(count0!=count1)
		{
			printf("NO\n");
		//	return 0;
			continue;
		}
		memset(borad,0,sizeof(borad));
		for(i=1;i<=m;i++)
		{
			for(j=1;j<=n;j++)
			{
				if((i+j)%2==0)
				{
					if(dian(i+1,j)&&map[i+1][j].color!=2)
					{
						borad[map[i][j].index][map[i+1][j].index]=1;
					}
					if(dian(i-1,j)&&map[i-1][j].color!=2)
					{
						borad[map[i][j].index][map[i-1][j].index]=1;
					}
					if(dian(i,j+1)&&map[i][j+1].color!=2)
					{
						borad[map[i][j].index][map[i][j+1].index]=1;
					}
					if(dian(i,j-1)&&map[i][j-1].color!=2)
					{
						borad[map[i][j].index][map[i][j-1].index]=1;
					}
				}
			}
		}
		/*for(i=0;i<count0;i++)
		{
		for(j=0;j<count0;j++)
		{
		printf("%d ",borad[i][j]);
		}
		printf("\n");
	}*/
		memset(pipei,-1,sizeof(pipei));
		ans=0;
		for(i=0;i<count0;i++)
		{
			memset(vist,0,sizeof(vist));
			if(dfs(i)) ans++;
		}
		if(ans==count0)
		{
			printf("YES\n");
		}
		else
		{
			printf("NO\n");
		}
	}
	return 0;
}
4 4 3
1 4
2 1
4 2
4 4 2
1 4
4 2
8 8 1
4 5
12 27 3
1 1
5 5
3 4
12 27 0
3 3 3
2 2
1 2
2 3

5 5 9
3 4
2 3
3 3
4 5
2 2
1 1
4 4
2 4
5 4

30 30 12
23 24
2 4
3 5
4 19
18 3
3 4
8 3
3 5
3 6
10 30
10 29
15 15

5 6 17
1 2
2 2
3 2
4 2
5 2
6 2
1 3
2 3
3 3
4 3

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