题目链接

 

题解：

我们可以对棋盘进行黑白染色，使得任意相邻的两个格子颜色不相同，然后进行二分图最大匹配。

 Code:

 1 class Solution {
 2 public:
 3     int N;
 4     int M;
 5 
 6     vector<vector<int>> dir{{1,0},{0,1},{-1,0},{0,-1}};
 7 
 8     int domino(int n, int m, vector<vector<int>>& broken) {
 9         N=n;
10         M=m;
11         vector<vector<int>> grid(N*M,vector<int>(N*M,0));
12         vector<int> bro(N*M,0);
13         for(auto b:broken){
14             bro[b[0]*M+b[1]]=1;
15         }
16         for(int i=0;i<N*M;++i){
17             if(bro[i]) continue;
18             int x=i/M;
19             int y=i%M;
20             if((x+y)%2!=0) continue;
21             for(int d=0;d<4;++d){
22                 int nx=x+dir[d][0];
23                 int ny=y+dir[d][1];
24                 if(nx<0 || nx>=N || ny<0 || ny>=M || bro[nx*M+ny]) continue;
25                 grid[i][nx*M+ny]=1;
26             }
27         }
28         vector<int> mat(N*M,-1);
29         int res=0;
30         for(int i=0;i<N*M;++i){
31             if(bro[i]) continue;
32             int x=i/M;
33             int y=i%M;
34             if((x+y)%2==0){
35                 vector<int> visited(N*M,0);
36                 if(dfs(i,grid,visited, mat)){
37                     res++;
38                 }
39             }
40         }
41         return res;
42     }
43 
44     bool dfs(int u, vector<vector<int>> &grid, vector<int> &visited, vector<int> &mat){
45         for(int i=0;i<M*N;++i){
46             if(grid[u][i]){
47                 if(!visited[i]){
48                     visited[i]=1;
49                     if(mat[i]==-1 || dfs(mat[i],grid,visited,mat)){
50                         mat[i]=u;
51                         return true;
52                     }
53                 }
54             }
55         }
56         return false;
57     }
58 };