传送门：点击打开链接
题意：一个地图中，有一些障碍，然后有其他的空白位置，现在问是否能用1*2的骨牌覆盖所有的空白位置，骨牌不能有重叠。
思路：乍看有点像状压dp，又有点像搜索，但是正解是二分图的最大匹配，而且做起来特别简单。
首先，我们枚举每一个空白的点，枚举四个方向，如果相邻的格子也为空白的，那么就在两个格子之间连一条边，很容易证明，这样的连线方法一定是二分图。
因为所有的格子，能通过(i+j)%2来分成两组，而这样连线刚好是两个点分别在其中的一组。
之后，我只要跑一遍二分图，看最大匹配*2是否刚好等于空格子的数量，就知道是否能完全覆盖了！
#include<map>
#include<set>
#include<cmath>
#include<ctime>
#include<stack>
#include<queue>
#include<cstdio>
#include<cctype>
#include<bitset>
#include<string>
#include<vector>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<functional>
#define fuck(x) cout<<"["<<x<<"]"
#define FIN freopen("input.txt","r",stdin)
#define FOUT freopen("output.txt","w+",stdout)
//#pragma comment(linker, "/STACK:102400000,102400000")
using namespace std;
typedef long long LL;const int MX = 3e3 + 5;
const int MS = 2e5 + 5;
int Head[MX], erear;
struct Edge {int v, nxt;
} E[MS];
void edge_init() {erear = 0;memset(Head, -1, sizeof(Head));
}
void edge_add(int u, int v) {E[erear].v = v;E[erear].nxt = Head[u];Head[u] = erear++;
}int match[MX];
bool vis[MX];
bool DFS(int u) {for(int i = Head[u]; ~i; i = E[i].nxt) {int v = E[i].v;if(!vis[v]) {vis[v] = 1;if(match[v] == -1 || DFS(match[v])) {match[v] = u;return 1;}}}return 0;
}
int BM(int n) {int res = 0;memset(match, -1, sizeof(match));for(int u = 1; u <= n; u++) {memset(vis, 0, sizeof(vis));if(DFS(u)) res++;}return res;
}int maz[100][100];
int dist[][2] = {
{0, 1}, {0, -1}, {1, 0}, { -1, 0}};
int main() {int n, m, k; //FIN;while(~scanf("%d%d%d", &n, &m, &k)) {edge_init();memset(maz, 0, sizeof(maz));for(int i = 1; i <= k; i++) {int x, y;scanf("%d%d", &x, &y);maz[y][x] = 1;}for(int i = 1; i <= n; i++) {for(int j = 1; j <= m; j++) {if(maz[i][j]) continue;for(int k = 0; k < 4; k++) {int nx = i + dist[k][0], ny = j + dist[k][1];if(nx < 1 || nx > n || ny < 1 || ny > m || maz[nx][ny]) continue;edge_add(i * m + j - m, nx * m + ny - m);edge_add(nx * m + ny - m, i * m + j - m);}}}int sz = n * m - k;if(sz % 2 == 0 && BM(n * m) == sz) printf("YES\n");else printf("NO\n");}return 0;
}