附上我的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;
}

• Re:弱弱的问一下，为什么这题就必须用二分，而用BFS或者DFS就错呢？ (17) walkbird 2012-02-21 16:22:13