題意：
? ? ? 給你一個(gè)n*m的格子，問你能不能用1*2的格子把他鋪滿，有的位置是不能被鋪的。
思路：

? ? ?水題，直接把個(gè)相鄰的并且都是可以鋪的點(diǎn)連一條邊然后匹配一遍就行了，提醒一個(gè)地方，就是輸入不能鋪的坐標(biāo)的時(shí)候是 先輸入列再輸入行。

#include<stdio.h> #include<string.h>#define N_node 1500 #define N_edge 6000typedef struct {int to ,next; }STAR;STAR E[N_edge]; int list[N_node] ,tot; int mk_dfs[N_node] ,mk_gx[N_node]; int map[40][40];void add(int a ,int b) {E[++tot].to = b;E[tot].next = list[a];list[a] = tot; }int DFS_XYL(int x) {for(int k = list[x] ;k ;k = E[k].next){int to = E[k].to;if(mk_dfs[to]) continue;mk_dfs[to] = 1;if(mk_gx[to] == -1 || DFS_XYL(mk_gx[to])){mk_gx[to] = x;return 1;}}return 0; }int main () {int n ,m ,k ,i ,j;int a ,b;while(~scanf("%d %d %d" ,&n ,&m ,&k)){memset(map ,0 ,sizeof(map));for(i = 1 ;i <= k ;i ++){scanf("%d %d" ,&b ,&a);map[a][b] = 1;}memset(list ,0 ,sizeof(list));tot = 1;for(i = 1 ;i <= n ;i ++)for(j = 1 ;j <= m ;j ++){if(map[i][j]) continue;int now = (i - 1) * m + j;if(i < n && !map[i+1][j])add(now ,now + m);if(j < m && !map[i][j+1])add(now ,now + 1);if(i > 1 && !map[i-1][j])add(now ,now - m);if(j > 1 && !map[i][j-1])add(now ,now - 1);}int sum = 0;memset(mk_gx ,255 ,sizeof(mk_gx));for(i = 1 ;i <= n * m ;i ++){memset(mk_dfs ,0 ,sizeof(mk_dfs));sum += DFS_XYL(i);}if(sum == n * m - k)puts("YES");else puts("NO");}return 0; }

總結(jié)

以上是生活随笔為你收集整理的POJ2446 二分匹配的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。