[POJ]2446 ChessBoard

Alice and Bob often play games on chessboard. One day, Alice draws a board with size M * N. She wants Bob to use a lot of cards with size 1 * 2 to cover the board. However, she thinks it too easy to bob, so she makes some holes on the board (as shown in the figure below). 

We call a grid, which doesn’t contain a hole, a normal grid. Bob has to follow the rules below: 
1. Any normal grid should be covered with exactly one card. 
2. One card should cover exactly 2 normal adjacent grids. 

Some examples are given in the figures below: 

A VALID solution.

An invalid solution, because the hole of red color is covered with a card.

An invalid solution, because there exists a grid, which is not covered.
Your task is to help Bob to decide whether or not the chessboard can be covered according to the rules above.

如果我们把每个棋盘的格子看做顶点，相邻的格子有边相连的话，那么棋盘就可以表示成一个二分图，因为只有黑色的格子和白色的格子之间才有边连接。黑色和黑色，白色和白色之间都没有边相连。那么这道题就相当于建图之后求最大匹配是否能覆盖图中的所有节点，求最大匹配的算法参考这篇文章。时间复杂度O(V*E)，代码如下：

	//POJ 2446
	/*
	Alice and Bob often play games on chessboard. One day, Alice draws a board with size M * N. She wants Bob to use a lot of cards with size 1 * 2 to cover the board. However, she thinks it too easy to bob, so she makes some holes on the board (as shown in the figure below).
	We call a grid, which doesn’t contain a hole, a normal grid. Bob has to follow the rules below:
	1. Any normal grid should be covered with exactly one card.
	2. One card should cover exactly 2 normal adjacent grids.
	Your task is to help Bob to decide whether or not the chessboard can be covered according to the rules above.
	Input
	There are 3 integers in the first line: m, n, k (0 < m, n <= 32, 0 <= K < m * n), the number of rows, column and holes. In the next k lines, there is a pair of integers (x, y) in each line, which represents a hole in the y-th row, the x-th column.
	Output
	If the board can be covered, output "YES". Otherwise, output "NO".
	*/
	#include <cstdio>
	#include <cstring>
	#include <utility>
	using namespace std;
	const int MAXN = 37;
	int match[MAXN * MAXN], visited[MAXN * MAXN], hole[MAXN * MAXN];
	int R, C, K;
	pair<int, int> dirs[4] = { { 1, 0 },{ 0, 1 },{ 0, -1 },{ -1, 0 } };
	bool valid(int x, int y)
	{
	return x >= 0 && x < R && y >= 0 && y < C;
	}
	bool dfs(int u)
	{
	int i = u / C, j = u % C, curr = i * C + j;
	if (visited[curr] == 1)return false;
	visited[curr] = 1;
	for (int k = 0; k < 4; ++k)
	{
	int x = i + dirs[k].first, y = j + dirs[k].second, next = x * C + y;
	if (valid(x, y) && !hole[next])
	{
	if (match[next] == -1 || dfs(match[next]))
	{
	match[curr] = next;
	match[next] = curr;
	return true;
	}
	}
	}
	return false;
	}
	int hungarian()
	{
	int totalMatch = 0;
	//we only need to dfs tile with single color(black or white)
	for (int i = 0; i < R; ++i)
	{
	for (int j = i % 2 ? 1 : 0; j < C; j += 2)
	{
	int idx = i * C + j;
	if (!hole[idx] && match[idx] == -1)
	{
	memset(visited, 0, sizeof(visited));
	if (dfs(idx))++totalMatch;
	}
	}
	}
	return totalMatch;
	}
	int main()
	{
	while (scanf("%d%d%d", &R, &C, &K) == 3)
	{
	memset(match, -1, sizeof(match));
	memset(hole, 0, sizeof(hole));
	//update holes
	for (int i = 0; i < K; i++)
	{
	int x, y;
	scanf("%d%d", &x, &y);
	hole[(y - 1) * C + x - 1] = 1;
	}
	//run hungarian to find max match
	int matches = hungarian();
	printf("%s\n", matches * 2 == (R * C - K) ? "YES" : "NO");
	}
	return 0;
	}

view raw POJ_2446_ChessBoard.cpp hosted with ❤ by GitHub