poj-2446-Chessboard
Chessboard
| Time Limit: 2000MS | Memory Limit: 65536K | |
| Total Submissions: 19476 | Accepted: 6147 |
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
Hint
A possible solution for the sample input.
Source
POJ Monthly,charlescpp
| 17930785 | 2446 | Accepted | 4520K | 63MS | G++ | 1399B | 2017-12-08 10:55:23 |
二分图匹配问题。
题意：对于 Grid 中 非hole，能否用 1x2 的砖块铺满。
首先检验剩余砖块是否偶数。然后使用匈牙利算法进行匹配，解决。
// poj-2446
#include <cstdio>
#include <cstring>
const int MAXN = 35;
const int dx[4] = {0, 0, -1, 1};
const int dy[4] = {-1, 1, 0, 0};
int n, m, k, mp[MAXN][MAXN], vis[MAXN*MAXN], match[MAXN*MAXN];
int len[MAXN*MAXN], vt[MAXN*MAXN][MAXN*MAXN];
bool dfs(int x){
for(int i=0; i<len[x]; ++i){
int y = vt[x][i];
if(vis[y] == 0){
vis[y] = 1;
if(match[y] < 0 || dfs(match[y])){
match[y] = x;
return true;
}
}
}
return false;
}
int main(){
freopen("in.txt", "r", stdin);
int x, y, ans;
while(scanf("%d %d %d", &n, &m, &k) != EOF){
memset(mp, 0, sizeof(mp));
for(int i=0; i<k; ++i){
scanf("%d %d", &x, &y);
mp[y][x] = 1;
}
if((m*n - k)%2 != 0){
printf("NO
");
continue;
}
memset(len, 0, sizeof(len));
for(int i=1; i<=n; ++i){
for(int j=1; j<=m; ++j){
if(mp[i][j] == 0){
int c = (i - 1)*m + j;
for(int k=0; k<4; ++k){
int nx = i + dx[k];
int ny = j + dy[k];
if(nx>=1 && nx<=n && ny>=1 && ny<=m && mp[nx][ny] == 0){
vt[ c ][ len[c] ] = m*(nx - 1) + ny;
++len[c];
}
}
}
}
}
memset(match, -1, sizeof(match));
ans = 0;
for(int i=1; i<=n; ++i){
for(int j=1; j<=m; ++j){
int c = (i - 1)*m + j;
memset(vis, 0, sizeof(vis));
if(dfs(c)){
++ans;
}
}
}
if(ans*2 == (n*m - k)){
printf("YES
");
}else{
printf("NO
");
}
}
return 0;
}