首页 > 代码库 > POJ 2446-Chessboard(二分图_最大匹配)
POJ 2446-Chessboard(二分图_最大匹配)
Chessboard
Time Limit: 2000MS | Memory Limit: 65536K | |
Total Submissions: 14157 | Accepted: 4401 |
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的矩阵(m是列,n是行),有k个点有洞,问2*1的木板是否可以将剩下的铺满,如果可以,输出yes,否则输出no。
思路:将有洞的格子标记,然后将剩下的格子链接相邻的。差点超时。看到网上有人用奇偶分。
#include <stdio.h> #include <math.h> #include <string.h> #include <stdlib.h> #include <iostream> #include <algorithm> #include <set> #include <queue> using namespace std; const int inf=0x3f3f3f3f; int map[2010][2010]; int G[2010][2010]; int vis[2010]; int link[2010]; int n,m; int cnt; int jx[]={1,-1,0,0}; int jy[]={0,0,1,-1}; int dfs(int u) { int i; for(i=1; i<=cnt; i++) { if(!vis[i]&&map[u][i]) { vis[i]=1; if(link[i]==-1||dfs(link[i])) { link[i]=u; return 1; } } } return 0; } int main() { int k,i,j,l; int a,b; while(~scanf("%d %d %d",&m,&n,&k)) { memset(map,0,sizeof(map)); memset(link,-1,sizeof(link)); memset(G,0,sizeof(G)); cnt=0; for(i=1; i<=k; i++) { scanf("%d %d",&b,&a); G[a][b]=-1; } for(i=1;i<=m;i++) { for(j=1;j<=n;j++) { if(!G[i][j]) G[i][j]=++cnt; } } for(i=1; i<=m; i++) { for(j=1; j<=n; j++) { if(G[i][j]!=-1) for(l=0;l<4;l++) { int x=i+jx[l]; int y=j+jy[l]; if(x>=1&&x<=m&&y>=1&&y<=n) { map[G[i][j]][G[x][y]]=1; } } } } int sum=0; for(i=1; i<=cnt; i++) { memset(vis,0,sizeof(vis)); if(dfs(i)) sum++; } if(sum==cnt) printf("YES\n"); else printf("NO\n"); } return 0; }
POJ 2446-Chessboard(二分图_最大匹配)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。