| Time Limit: 2000MS |
|
Memory Limit: 65536K |
| Total Submissions: 8985 |
|
Accepted: 2740 |
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.
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
参考程序
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N = 35;
const int dx[] = {-1, 1, 0, 0},
dy[] = { 0, 0,-1, 1};
int m,n,k,oddn,even,match[N*N/2],number[N][N];
int adj[N*N/2][5];
bool used[N*N],ishole[N][N];
bool init(){
memset(match,0,sizeof(match));
memset(used,0,sizeof(used));
memset(ishole,0,sizeof(ishole));
memset(adj,0,sizeof(adj));
cin>>m>>n>>k;
if ((m*n-k)%2) return false;
for (int i=0,x,y;i<k;i++){
cin>>y>>x;
ishole[x][y]=true;
}
oddn=even=0;
for (int i=1;i<=m;i++)
for (int j=1;j<=n;j++){
if (ishole[i][j]) continue;
if ((i+j)%2)
number[i][j] = ++oddn;
else number[i][j] = ++even;
}
int x1,y1;
for (int x=1;x<=m;x++)
for (int y=1;y<=n;y++)
if (!ishole[x][y] && (x+y)%2){
for (int i=0;i<4;i++){
x1 = x+dx[i];
y1 = y+dy[i];
if (x1<1 || x1>m || y1<1 || y1>n) continue;
if (ishole[x1][y1]) continue;
adj[number[x][y]][++adj[number[x][y]][0]]=number[x1][y1];
}
}
if (oddn!=even) return false;
return true;
}
bool can(int k){
for (int i=1;i<=adj[k][0];i++){
int j=adj[k][i];
if (!used[j])
{
used[j]=true;
if (!match[j]||can(match[j]))
{
match[j]=k;
return true;
}
}
}
return false;
}
bool covered(){
int matchn=0;
for (int i=1;i<=oddn;i++){
if (can(i))
matchn++;
memset(used,0,sizeof(used));
}
if (matchn*2==m*n-k) return true;
else return false;
}
int main(){
if (init())
if (covered()) cout<<"YES\n";
else cout<<"NO\n";
else cout<<"NO\n";
}.
posted on 2011-10-26 17:06
龙在江湖 阅读(198)
评论(0) 编辑 收藏 引用 所属分类:
图论 、
竞赛题解_POJ