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或者DFS就错呢?

Posted by tytzyl at 2009-03-31 15:45:33 on Problem 2446
附上我的BFS代码,当然结果是wrong answer,只是希望能知道有什么地方没考虑到。
#include<stdio.h>
#include<memory.h>

const int maxn = 40;
typedef struct{
	int x, y, color;
}type;
bool chosen[maxn][maxn] ;
int m, n;
bool check(int i, int j)
{
	if(i >= 1 && i <= m && j >= 1 && j <= n && !chosen[i][j])
		return true;
	else
		return false;
}
int main()
{
	int i, j, k, x, y, front, tail, sum;
	bool flag;
	type que[maxn*maxn], s;

	while(scanf("%d%d%d", &m, &n, &k) != EOF)
	{
		memset(chosen, false, sizeof(chosen));
		for(i = 0; i < k; i++)
		{
			scanf("%d%d", &y, &x);
			chosen[x][y] = true;
		}
		flag = true;
		for(i = 1; i <= m && flag; i++)
			for(j = 1; j <= n && flag; j++)
			{
				if(!chosen[i][j])
				{
					front = tail = 0;
					que[front].color = 0;
					que[front].x = i;
					que[front].y = j;
					chosen[i][j] = true;
					sum = 1;
					while(tail <= front)
					{
						s = que[tail++];
						if(check(s.x+1, s.y))
						{
							chosen[s.x+1][s.y] = true;
							que[++front].x = s.x + 1;
							que[front].y = s.y;
							que[front].color = (s.color + 1)%2;
							if(que[front].color == 0)
								sum ++;
							else
								sum --;
						}

						if(check(s.x-1, s.y))
						{
							chosen[s.x-1][s.y] = true;
							que[++front].x = s.x - 1;
							que[front].y = s.y;
							que[front].color = (s.color + 1)%2;
							if(que[front].color == 0)
								sum ++;
							else
								sum --;
						}

						if(check(s.x, s.y + 1))
						{
							chosen[s.x][s.y + 1] = true;
							que[++front].x = s.x;
							que[front].y = s.y + 1;
							que[front].color = (s.color + 1)%2;
							if(que[front].color == 0)
								sum ++;
							else
								sum --;
						}

						if(check(s.x, s.y - 1))
						{
							chosen[s.x][s.y - 1] = true;
							que[++front].x = s.x;
							que[front].y = s.y - 1;
							que[front].color = (s.color + 1)%2;
							if(que[front].color == 0)
								sum ++;
							else
								sum --;
						}
					}
					if(sum != 0)
					{
						flag = false;
					}
				}
			}
			if(flag == true)
				printf("YES\n");
			else
				printf("NO\n");
	}
	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