<题目链接>
题目大意:
给你一个n*m的棋盘,其中有k个洞,现在有1*2大小的纸片,纸片不能覆盖洞,并且每个格子最多只能被覆盖一次。问你除了洞口之外这个棋盘是否能被纸片填满。
解题分析:
还有一种根据横、纵坐标之和奇偶性,将棋盘上所有的点分成二部图两部分,然后用匈牙利算法求解的方法。
#include <cstdio> #include <cstring> #define N 34 #define M N*N ], used[M], mat[M]; int match, m, n; bool find(int k){ ; i<=g[k][]; i++) //遍历序号为k的点的所有能够和它匹配的点 { int j = g[k][i]; if(!used[j]) { used[j] = ; if(!mat[j] || find(mat[j])) //如果这个点没有归属点或者它的归属点能够和其它点进行匹配 { mat[j] = k; //那么更换这个点的归属点 return true; } } } return false; } void Hungary() { ; i<=m*n; i++) //枚举每个点 { ] != - && g[i][] != ) //如果这个点不是hole 并且 它有点可供它配对 { memset(used, , sizeof(used)); match += find(i); //如果配对成功,+1 } } } int main() { int i, j; int k; int x, y; scanf("%d%d%d", &m, &n, &k); ; i<=k; i++) { scanf("%d%d", &y, &x); //注意这个题目的输入有坑 g[y+(x-)*n][] = -; } ; i<=m*n; i++) //由于卡片长度为2,所以每个点只能和它周围相邻的点配对,所以先把所有点的所有能和它配对的点全部找出来 { ] != -) { //left )%n >= && g[i-][] != -) //它左边有点且该点能够匹配 g[i-][++g[i-][]] = i; //那么就记录下这两个点的匹配关系 //right && g[i+][] != -) g[i+][++g[i+][]] = i; //up && g[i-n][] != -) g[i-n][++g[i-n][]] = i; //down ) / n <= m && g[i+n][] != -) g[i+n][++g[i+n][]] = i; } } match = ; Hungary(); //匈牙利 if(match == m*n-k) printf("YES\n"); else printf("NO\n"); ; }
2018-08-15