LCP 04-覆盖

Raphael Liu Lv10
  2023-09-13 00:47:26 2023-09-13 00:47:26 Created   2023-09-13 16:06:27 2023-09-13 16:06:27 Updated    

你有一块棋盘，棋盘上有一些格子已经坏掉了。你还有无穷块大小为1 * 2的多米诺骨牌，你想把这些骨牌 不重叠 地覆盖在 完好
的格子上，请找出你最多能在棋盘上放多少块骨牌？这些骨牌可以横着或者竖着放。

输入：n, m代表棋盘的大小；broken是一个b * 2的二维数组，其中每个元素代表棋盘上每一个坏掉的格子的位置。

输出：一个整数，代表最多能在棋盘上放的骨牌数。

示例 1：

**输入：** n = 2, m = 3, broken = [[1, 0], [1, 1]]
**输出：** 2
**解释：** 我们最多可以放两块骨牌：[[0, 0], [0, 1]]以及[[0, 2], [1, 2]]。（见下图）

![](https://assets.leetcode-cn.com/aliyun-lc-
upload/uploads/2019/09/09/domino_example_1.jpg)

示例 2：

**输入：** n = 3, m = 3, broken = []
**输出：** 4
**解释：** 下图是其中一种可行的摆放方式

![](https://assets.leetcode-cn.com/aliyun-lc-
upload/uploads/2019/09/09/domino_example_2.jpg)

限制：

  1. 1 <= n <= 8
  2. 1 <= m <= 8
  3. 0 <= b <= n * m

关注小爱老师的算法课堂 ，分享高质量算法视频与文字题解

题目分析：二分图最大匹配

我们首先可以将棋盘抽象成 x, y 交替的格子：x 周围均为 y，y 周围均为 x，如下图所示：
image.png

那么，一个多米诺骨牌一定占据一个 x 格子及一个 y 格子，且这两个格子必须相邻。也就是说，棋盘中的每个 x 相连的点均为 y，而所有的 y 相连的点均为 x。这就抽象成了一个二分图（二分图的定义可以参考785. 判断二分图 ），而我们要放置最多的多米诺骨牌，也就是找到一种方式，使得二分图中连的边数量最大。这就是典型的二分图最大匹配。

二分图最大匹配问题，一般可以用匈牙利算法解决。在介绍匈牙利算法之前，我们需要明确一些专有名词：

  1. 匹配集合：我们最终的目标是最大化边的数量，这些边将加入匹配集合。
  2. 匹配边、匹配点：在二分图中，如果我们本次将两个点连成的边加入匹配集合，就说我们当前将这条边作为了匹配边，边的两个端点均称作匹配点。
  3. 未匹配边、未匹配点：在二分图中，如果一个点有一条以上的边，并且其中某一条边已经被加入了匹配集合成为了匹配边，那么剩余的边均称作未匹配边，这些边的另一个端点称为未匹配点。
  4. 增广路：以未匹配边开始和结束，且未匹配边与匹配边交替出现的路径。

为了便于大家理解，我们通过下图（红框和篮框分别表示二分图中的两部分，黑色圆圈表示不同的点。黄色和绿色线条都表示点之间的边）来解释上面 4 个概念：
image.png

我们首先将 1 号点和 5 号点之间的边放入匹配集合，该边就变成了匹配边（黄色标识）。1 和 5 号点就均变为了匹配点，此时，这两个点连接的其他边（(1, 7), (2, 5), (4, 5)）就称作未匹配边，对应的点 2, 4, 7 就均称作未匹配点。我们其次将 3 号点和 6 号点之间的边放入匹配集合，该边就变成了匹配边，这两个点变为了匹配点。由于这两个点没有连其他的边，所以不会出现新的未匹配边。

此时，我们发现，路径 2-5-1-7 就是一条 未匹配边-匹配边-未匹配边 组合的增广路径。

明确了这些概念后，我们便来看我们的匈牙利算法：

  1. 初始时，最大匹配集合为空。
  2. 我们先找到一组匹配边，加入匹配集合。
  3. 找到一条增广路径，我们将其中的所有匹配边变为未匹配边，将所有的未匹配边变为匹配边。
  4. 循环步骤 3，直到图中不存在增广路径。算法结束

匈牙利算法中，最重要的便是步骤 3。我们来深入理解一下：

对于一条增广路径，根据其定义，必定含有 k + 1 条未匹配边以及 k 条匹配边。那么，步骤 3 的作用，其实就是将未匹配边和匹配边互换，这样，该路径上就会更新为 k 条未匹配边以及 k + 1 条匹配边，这样匹配边的数量就比互换之前多了 1 个。结合刚才的图片来看：
image.png

我们将增广路径 2-5-1-7 上的未匹配边 (2, 5), (1, 7) 变为匹配边，将匹配边 (5, 1) 变为未匹配边，图中总匹配边数就从原来的两条（(1, 5), (3, 6)）变成了三条（(2, 5), (1, 7), (3, 6)）。

以上就是我们的匈牙利算法啦！在代码中，我们使用了二分图模板 BinaryGraph 类初始化二分图，利用其中的 add 函数完成加边，并利用其中的 solve 方法即可直接求得最大匹配。

算法细节：

首先，我们要初始化二分图。初始化方法 init 需要两个参数 n_1, n_2，分别为两个部分中点的数量，为了方便起见，我们可以直接令 n_1 = n_2 = n，因为最终进行最大匹配是根据边来求解的，点的数量不会影响该过程。

其次，我们需要利用 add 方法进行加边。一般情况下，我们需要预处理，先将题目给定的图标识成二分图（比如一部分标识为 0，另一部分标识为 1）。但在本题中，棋盘上第 i 行第 j 列属于哪一部分可以直接根据 i + j 的奇偶性得到。

然后，我们可以通过深度优先搜索遍历每个点，将该点连向四周的点。特别地，在二分图中，只需要从一个集合向另一个集合连有向边即可，不需要双向连边。在代码中，我们从偶数部分向奇数部分连边。另外，本题中棋盘上有些点不可以放多米诺骨牌，在连边过程中进行特判即可。

最终，我们直接利用二分图类中的 solve 方法即可求解。具体可见代码。

代码

[]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
class BinaryGraph {
public: 
    vector<vector<int> > g;
    vector<int> pa;  // 匹配
    vector<int> pb;
    vector<int> vis;  // 访问
    int n, m;         // 两个点集中的顶点数量
    int dfn;          // 时间戳记
    int res;          // 匹配数

    // 二分图初始化
    void init(int _n, int _m) {
        n = _n;
        m = _m;
        pa = vector<int>(n, -1);
        pb = vector<int>(m, -1);
        vis = vector<int>(n);
        g.resize(n);
        res = 0;
        dfn = 0;
    }

    // 加边函数
    void add(int from, int to) {
        g[from].push_back(to);
    }

    // 最大匹配
    bool dfs(int v) {
        vis[v] = dfn;
        for (int u : g[v]) {
            if (pb[u] == -1) {
                pb[u] = v;
                pa[v] = u;
                return true;
            }
        }
        for (int u : g[v]) {
            if (vis[pb[u]] != dfn && dfs(pb[u])) {
                pa[v] = u;
                pb[u] = v;
                return true;
            }
        }
        return false;
    }

    int solve() {
        while (true) {
            dfn++;
            int cnt = 0;
            for (int i = 0; i < n; i++) {
                if (pa[i] == -1 && dfs(i)) {
                    cnt++;
                }
            }
            if (cnt == 0) {
                break;
            }
            res += cnt;
        }
        return res;
    }
};

class Solution {
public:
    int x[4] = {-1, 0, 1, 0};
    int y[4] = {0, 1, 0, -1};

    int domino(int n, int m, vector<vector<int>>& broken) {
        // 建图，若为 0 则不能放多米诺骨牌，否则可以放置
        vector<vector<int>> graph(n, vector<int>(m, 1));
        for(auto b : broken) graph[b[0]][b[1]] = 0;

        // 初始化二分图
        BinaryGraph *bg = new BinaryGraph();
        bg->init(n * m, n * m);

        // 深度优先搜索，加边
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < m; j++) {
                if(!graph[i][j]) continue;
                // (i, j) -> 四边扩展
                for(int k = 0; k < 4; k++) {
                    int dx = i + x[k], dy = j + y[k];
                    if(dx < 0 || dx >= n || dy < 0 || dy >= m || !graph[dx][dy]) continue;
                    if((i + j) % 2 == 0) bg->add(i * m + j, dx * m + dy);
                }
            }
        }
        
        // 求解
        return bg->solve();
    }
};

复杂度分析：

  • 时间复杂度：O(n^2m^2)，匈牙利算法每次选择图中一个顶点，寻找增广路径。寻找增广路径最多会遍历图中所有边，故总复杂度为 O(EV)，其中 E 为点数量，V 为边数量。又因为每个点最多连出 4 条边，且点数量为 nm，故总复杂度大约在 O(n^2m^2) 量级。
 Comments
On this page
LCP 04-覆盖
  1. 题目分析：二分图最大匹配
  2. 算法细节：
  3. 代码
  4. 复杂度分析：