本文主要是介绍POJ 2446 Chessboard，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
链接：http://poj.org/problem?id=2446
题目：
Chessboard
| Time Limit: 2000MS | Memory Limit: 65536K | |
| Total Submissions: 12573 | Accepted: 3907 |
Description
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.
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.
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".
Sample Input
4 3 2 2 1 3 3
Sample Output
YES
解题思路：
这是一个二分图的最大匹配问题，我是把m*n的方格用一个数num来表示，这个num作为集合X的元素，对应集合Y中的元素，是与之相邻的点的坐标。我们先要把hole点处理掉，不要放到集合Y中。再用一下匈牙利算法就可以了。
代码：
#include <iostream>
#include <cstdio>
#include <vector>
#include <cstring>
using namespace std;const int MAXN = 40;
int n, m, k, vis[MAXN][MAXN], match[MAXN][MAXN], map[MAXN][MAXN];
struct Point
{int x, y;
};
vector<Point> g[MAXN*MAXN];void add(int i, int j, int num)
{Point p;if(j - 1 >= 1 && match[i][j-1]){p.x = i; p.y = j - 1; g[num].push_back(p);}if(j + 1 <= n && match[i][j+1]) {p.x = i; p.y = j + 1; g[num].push_back(p);}if(i - 1 >= 1 && match[i-1][j]) {p.x = i - 1; p.y = j; g[num].push_back(p);}if(i + 1 <= m && match[i+1][j]) {p.x = i + 1; p.y = j; g[num].push_back(p);}
}int dfs(int x)
{int size = g[x].size();for(int i = 0; i < size; i++){Point p = g[x][i];if(!vis[p.x][p.y] && match[p.x][p.y]){vis[p.x][p.y] = 1;if(-1 == match[p.x][p.y] || dfs(match[p.x][p.y])){match[p.x][p.y] = x;return 1;}}}return 0;
}int main()
{for(int i = 1; i < MAXN*MAXN; i++){g[i].clear();}memset(match, -1, sizeof(match));memset(map, 0, sizeof(map));scanf("%d%d%d", &m, &n, &k);for(int i = 0; i < k; i++){int x, y;scanf("%d%d", &x, &y);match[y][x] = 0;}map[1][1] = 1;for(int i = 2; i <= n; i++) map[1][i] = !map[1][i-1];for(int i = 2; i <= m; i++){for(int j = 1; j <= n; j++){map[i][j] = !map[i-1][j];}}int num = 1;for(int i = 1; i <= m; i++){for(int j = 1; j <= n; j++){if(map[i][j] && match[i][j]){add(i, j, num);}num++;}}int ans = 0;for(int i = 1; i <= m * n; i++){memset(vis, 0, sizeof(vis));if(dfs(i)) ans++;}printf("%s\n", m * n == ans * 2 + k ? "YES" : "NO");return 0;
}这篇关于POJ 2446 Chessboard的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
