LeetCode LCP 04. 覆盖

2021-04-03 HGNULB 约 15 分钟

文章信息 6 个分类 6 个标签

分类

题目描述

✅ LCP 04. 覆盖

题意分析

一块 n × m 的棋盘，其中 broken 列出的格子已经损坏不可使用。现在用 1×2 的多米诺骨牌去铺，每张骨牌横放或竖放，覆盖两个相邻的完好格子，骨牌之间不能重叠。求最多能放多少张。

把题目翻译成图论语言：每张骨牌就是「一对相邻的完好格子」，而「骨牌之间不重叠」意味着每个格子最多被用一次。于是问题变成——在「格子为点、相邻完好格子间连边」的图上，选出尽可能多的边，使得这些边两两不共享端点。这正是最大匹配的定义。识别出这一步，整道题就从「怎么摆放」变成了一个标准图论问题。

进一步，棋盘有一个天然的性质：按 (r + c) 的奇偶给格子染成黑白两色，那么任意一对相邻格子必然一黑一白（横向或纵向移动一格，r + c 的奇偶必然翻转）。这说明这张图是二分图，黑格构成左部、白格构成右部，所有边都跨越两部。二分图最大匹配有成熟算法，而一般图的最大匹配要用带花树，复杂得多——所以染色这一步不是锦上添花，而是把问题拉进可解范围的关键。

约束里 n 与 m 都不超过 8，格子总数不超过 64，边数不超过 100 出头。规模极小，$O(V \cdot E)$ 的匈牙利算法绰绰有余，不必上 Hopcroft–Karp。规模小也提示了另一条路：状态压缩 DP 逐行转移同样可行（每行状态 $2^8$），两条路都是标准解。

边界方面：broken 可能为空（棋盘完好），也可能把整块棋盘占满（答案为 0）；损坏格子既不能作为骨牌的任一端，也不能被跨越，所以建图时两端都要检查完好性。

解法：二分图最大匹配（匈牙利算法）

核心思路

先说为什么不能贪心。「从左上往右下扫，遇到能放就放」这类策略会失败：某个位置的放置可能堵死后面两个更优的放置。举个直观的例子，一条 1×3 的走廊里，中间格如果被先来的骨牌以「左中」方式占住，右边的格子就孤立了；而实际上最优放法可能需要错开一格。局部选择会影响全局，贪心的「不劣性」证不出来。

暴力搜索则是枚举每个格子的放/不放，$2^{64}$ 级别，不可行。

正确的路径是上一节推出的建模：答案 = 二分图最大匹配数。匹配的定义（边两两不共端点）与骨牌不重叠完全对应，因此两者的最优值相等——每一组合法的骨牌摆放对应一组匹配，反之亦然。

求二分图最大匹配用匈牙利算法。它的核心是增广路：对左部的每个点 u 尝试为它找一个匹配对象，做法是遍历 u 的所有邻居 v——

若 v 尚未被匹配，直接把 u 与 v 配上，匹配数加一；

若 v 已被某个 u' 占用，就递归地问 u'：「你能不能换一个对象？」。如果 u' 能找到别的空位，那 v 就腾出来给 u，匹配数同样加一；如果 u' 也换不动，就继续尝试 u 的下一个邻居。

这个「让对方腾位置」的递归过程就是在寻找一条增广路。匈牙利算法的正确性由König 定理背后的增广路定理保证：一个匹配是最大匹配，当且仅当不存在增广路。所以对每个左部点各尝试一次增广，做完就是最大匹配。

维持的不变量是：处理完前 i 个左部点后，matchRight 描述的是「前 i 个左部点与右部之间的一个最大匹配」；每一轮增广要么让匹配数加一，要么证明当前点无法加入任何最大匹配（此时也不必再管它）。关键是增广过程只会改变匹配的配对方式，绝不会减少匹配总数——腾位置的那一方一定同时找到了新位置，这是递归返回 true 才执行改写的原因。

每次为一个新的左部点做增广时，seen 数组必须重新清零。它记录的是「本次增广中，右部点是否已经被尝试过」，作用是防止在交错路上绕圈死循环。它的作用域严格限定在一次增广内，跨轮复用会让后面的点找不到本可用的空位。

解题步骤

标记损坏格子：把 broken 里的坐标写进布尔矩阵 bad。为什么先做这一步：后面建图时要频繁判断格子是否可用，用矩阵查询是 $O(1)$，比每次遍历 broken 快得多也更清晰。

黑白染色并分别编号：遍历所有完好格子，(r + c) 为偶数的记进 leftId（左部），为奇数的记进 rightId（右部），各自从 0 开始连续编号。为什么要重新编号而不直接用 (r, c)：匈牙利算法要用一维数组存匹配关系与访问标记，连续编号能让这些数组紧凑且下标直观。为什么用 -1 作为「不属于该部或已损坏」的标记：便于建图时一眼跳过。

建邻接表：对每个左部格子，沿上下左右四个方向找邻居；邻居必须在棋盘内、未损坏，且它的 rightId 不为 -1，才把这条边加进 adj[u]。为什么只从左部往右部连单向边：二分图匹配只需从左部发起搜索，反向边用 matchRight 隐式表达即可，存双向反而浪费。为什么要判 bad[nr][nc]：损坏格子不能作为骨牌的另一端。

初始化 matchRight 为全 -1：语义是「每个右部点当前匹配到的左部点，-1 表示空闲」。

对每个左部点做一次增广：先给本轮开一个全新的 seen（长度为右部点数），再调 dfs(u)；返回 true 就把答案加一。为什么每轮都要新的 seen：它只服务于本次增广的防重，跨轮残留会误判「已尝试过」而错过可行位置。

增广的递归体：遍历 u 的邻居 v，跳过 seen[v] 为真的；标记 seen[v] = true；若 matchRight[v] == -1（空闲）或 dfs(matchRight[v]) 成功（原主人挪走了），就令 matchRight[v] = u 并返回 true。为什么标记要在递归之前：防止递归回到同一个 v 形成环。为什么改写 matchRight[v] 要在条件成立之后：只有确认整条增广路可行，才能落实改动，否则会破坏已有匹配。

返回答案：成功增广的次数即最大匹配数，也就是能放的骨牌数。

以 n = 2、m = 3、broken = [[1, 0], [1, 1]] 走一遍（预期答案 2）。
棋盘完好格子是 (0,0)、(0,1)、(0,2)、(1,2)。染色：(0,0) 的 r+c=0 为偶，是左部 0 号；(0,2) 的 r+c=2 为偶，是左部 1 号；(0,1) 的 r+c=1 为奇，是右部 0 号；(1,2) 的 r+c=3 为奇，是右部 1 号。
建图：左部 0 号 (0,0) 的四邻中只有 (0,1) 可用，adj[0] = [0]；左部 1 号 (0,2) 的四邻中 (0,1) 与 (1,2) 都可用，adj[1] = [0, 1]。
增广左部 0 号：seen 清零，尝试右部 0 号，它空闲，直接配对，matchRight[0] = 0，答案变 1。
增广左部 1 号：seen 清零，先尝试右部 0 号，标记 seen[0] = true；它已被左部 0 号占用，于是递归问左部 0 号能不能换——左部 0 号只有右部 0 号一个邻居，而它已被 seen 标记，递归返回 false。回到左部 1 号，继续尝试下一个邻居右部 1 号，它空闲，配对成功，matchRight[1] = 1，答案变 2。
返回 2，对应两张骨牌：(0,0)-(0,1) 与 (0,2)-(1,2)，正确。

这一趟正好展示了增广的两种分支：第一次是「直接占空位」，第二次先尝试「让对方腾位置」失败、再回退去找别的空位。若把 broken 改成 [[1,0]]，左部 0 号仍配右部 0 号，而左部 1 号会先尝试让左部 0 号挪走——左部 0 号此时多了一个邻居（(1,0) 若完好则属于右部），就能挪成功，从而整体匹配数增加，这正是增广路的价值。

代码实现

class Solution {
    private static final int[] DR = {-1, 1, 0, 0};
    private static final int[] DC = {0, 0, -1, 1};

    public int domino(int n, int m, int[][] broken) {
        boolean[][] bad = new boolean[n][m];
        for (int[] b : broken) {
            bad[b[0]][b[1]] = true;
        }

        int[][] leftId = new int[n][m];
        int[][] rightId = new int[n][m];
        for (int i = 0; i < n; i++) {
            Arrays.fill(leftId[i], -1);
            Arrays.fill(rightId[i], -1);
        }

        // 黑白染色：(r + c) 的奇偶决定归属，相邻格子必然异色。
        int leftCnt = 0;
        int rightCnt = 0;
        for (int r = 0; r < n; r++) {
            for (int c = 0; c < m; c++) {
                if (bad[r][c]) {
                    continue;
                }
                if (((r + c) & 1) == 0) {
                    leftId[r][c] = leftCnt++;
                } else {
                    rightId[r][c] = rightCnt++;
                }
            }
        }

        // 只从左部向右部建单向边，反向关系由 matchRight 隐式表达。
        List<Integer>[] adj = new List[leftCnt];
        for (int i = 0; i < leftCnt; i++) {
            adj[i] = new ArrayList<>();
        }
        for (int r = 0; r < n; r++) {
            for (int c = 0; c < m; c++) {
                if (leftId[r][c] == -1) {
                    continue;
                }
                int u = leftId[r][c];
                for (int d = 0; d < 4; d++) {
                    int nr = r + DR[d];
                    int nc = c + DC[d];
                    if (nr < 0 || nr >= n || nc < 0 || nc >= m || bad[nr][nc]) {
                        continue;
                    }
                    int v = rightId[nr][nc];
                    if (v != -1) {
                        adj[u].add(v);
                    }
                }
            }
        }

        int[] matchRight = new int[rightCnt];
        Arrays.fill(matchRight, -1);
        int answer = 0;
        for (int u = 0; u < leftCnt; u++) {
            // seen 只服务于本次增广，必须每轮重建。
            boolean[] seen = new boolean[rightCnt];
            if (dfs(u, adj, matchRight, seen)) {
                answer++;
            }
        }
        return answer;
    }

    private boolean dfs(int u, List<Integer>[] adj, int[] matchRight, boolean[] seen) {
        for (int v : adj[u]) {
            if (seen[v]) {
                continue;
            }
            seen[v] = true;
            // v 空闲，或它的原主人能腾走，都算增广成功。
            if (matchRight[v] == -1 || dfs(matchRight[v], adj, matchRight, seen)) {
                matchRight[v] = u;
                return true;
            }
        }
        return false;
    }
}

func domino(n int, m int, broken [][]int) int {
    bad := make([][]bool, n)
    for i := 0; i < n; i++ {
        bad[i] = make([]bool, m)
    }
    for _, b := range broken {
        bad[b[0]][b[1]] = true
    }

    leftId := make([][]int, n)
    rightId := make([][]int, n)
    for i := 0; i < n; i++ {
        leftId[i] = make([]int, m)
        rightId[i] = make([]int, m)
        for j := 0; j < m; j++ {
            leftId[i][j] = -1
            rightId[i][j] = -1
        }
    }

    // 黑白染色：(r + c) 的奇偶决定归属，相邻格子必然异色。
    leftCnt, rightCnt := 0, 0
    for r := 0; r < n; r++ {
        for c := 0; c < m; c++ {
            if bad[r][c] {
                continue
            }
            if (r+c)%2 == 0 {
                leftId[r][c] = leftCnt
                leftCnt++
            } else {
                rightId[r][c] = rightCnt
                rightCnt++
            }
        }
    }

    // 只从左部向右部建单向边，反向关系由 matchRight 隐式表达。
    adj := make([][]int, leftCnt)
    dr := []int{-1, 1, 0, 0}
    dc := []int{0, 0, -1, 1}
    for r := 0; r < n; r++ {
        for c := 0; c < m; c++ {
            if leftId[r][c] == -1 {
                continue
            }
            u := leftId[r][c]
            for d := 0; d < 4; d++ {
                nr, nc := r+dr[d], c+dc[d]
                if nr < 0 || nr >= n || nc < 0 || nc >= m || bad[nr][nc] {
                    continue
                }
                v := rightId[nr][nc]
                if v != -1 {
                    adj[u] = append(adj[u], v)
                }
            }
        }
    }

    matchRight := make([]int, rightCnt)
    for i := 0; i < rightCnt; i++ {
        matchRight[i] = -1
    }

    var dfs func(u int, seen []bool) bool
    dfs = func(u int, seen []bool) bool {
        for _, v := range adj[u] {
            if seen[v] {
                continue
            }
            seen[v] = true
            // v 空闲，或它的原主人能腾走，都算增广成功。
            if matchRight[v] == -1 || dfs(matchRight[v], seen) {
                matchRight[v] = u
                return true
            }
        }
        return false
    }

    answer := 0
    for u := 0; u < leftCnt; u++ {
        // seen 只服务于本次增广，必须每轮重建。
        seen := make([]bool, rightCnt)
        if dfs(u, seen) {
            answer++
        }
    }
    return answer
}

复杂度分析

时间复杂度：$O(V \cdot E)$，其中 V 是左部点数、E 是边数。凭什么：对每个左部点各做一次增广，单次增广最坏会遍历全部边一遍（每条边至多被走一次，由 seen 保证），因此总量是点数乘边数。代入本题约束，格子不超过 64、边不超过 112，实际运算量在万级以内，远低于时限。

空间复杂度：$O(V + E)$。凭什么：邻接表存下所有边是 $O(E)$；leftId、rightId、bad 三个矩阵合计 $O(n \cdot m)$；matchRight 与每轮的 seen 各是 $O(V)$；递归栈深度不超过左部点数。

关键点总结

「若干对相邻元素，每个元素最多用一次，求最多能选几对」是最大匹配的标准形态。看到这个形态就该往图论上靠，而不是纠结摆放顺序。

棋盘按 (r + c) 奇偶染色后相邻必异色，这是网格题里最常用的二分性证明；有了二分性才能用匈牙利算法，否则要上带花树，难度完全不同。

匈牙利算法的灵魂是增广路：不是「找空位」而是「找一条能让别人腾位置的链」。能把这句话讲清楚，就说明真的理解了它为什么能得到最大值而不是极大值。

seen 数组的作用域是一次增广，每轮必须重置；matchRight 的作用域是整个算法，全程保留。把两者的生命周期分清楚，是这段代码最容易写错的地方。

匹配关系只在递归确认成功后才写入，绝不能边试边改——否则失败的尝试会留下破损的匹配。

面试视角：先把「骨牌 = 边、不重叠 = 不共端点」的等价关系说出来，再讲染色得到二分图，最后才提匈牙利算法。建模那两步才是考点，算法本身是模板。若被追问其他解法，可以说棋盘只有 8 列，逐行做状态压缩 DP（用一个 8 位掩码表示本行哪些格子被上一行的竖放骨牌占用）同样是标准解，且复杂度更可控。

易错点总结

错误写法：每轮增广不重建 seen，复用同一个数组 → 用例 n = 2, m = 3, broken = [[1,0],[1,1]] 中左部 1 号发现右部 0 号已被标记而直接跳过腾位尝试，虽然本例侥幸仍得 2，但在需要连续多次腾位的棋盘上会漏掉匹配，答案偏小。

错误写法：在递归之前就写 matchRight[v] = u → 用例中一旦深层递归失败，已经被改写的匹配无法回滚，原有匹配被破坏，答案比真实值更小。

错误写法：seen[v] = true 写在递归之后 → 用例中两个左部点互相尝试对方的匹配对象时形成环，递归无限下降直至栈溢出。

错误写法：建图时只判邻居越界不判 bad[nr][nc] → 用例 broken = [[1,0],[1,1]] 中损坏格子被当成可用端点，骨牌被放到坏格上，答案偏大。

错误写法：染色用 r % 2 而不是 (r + c) % 2 → 用例中同一行的相邻格子被分到同一部，横放的骨牌对应的边根本建不出来，答案严重偏小。

错误写法：建双向边并对左右两部都发起增广 → 用例中每张骨牌被从两端各匹配一次，答案翻倍。

错误写法：直接用 (r, c) 的一维压缩值 r * m + c 当左右部编号，但 matchRight 只开 leftCnt 长度 → 用例中右部编号超出数组范围，Java 抛数组越界异常，Go 直接 panic。

错误写法：用贪心「从左上到右下，能横放就横放」 → 用例 n = 3, m = 3, broken = [[0,0],[2,2]] 中贪心会先占住中间格导致后续无处可放，答案比最大匹配小。

错误写法：把答案理解成「完好格子数除以 2」 → 用例 n = 1, m = 3, broken = [[0,1]] 中完好格子有两个但互不相邻，答案是 0 而不是 1。

错误写法：认为损坏格子只是「不能放骨牌」而仍可被跨越 → 骨牌只覆盖相邻两格，本就不存在跨越；但若据此在建图时把隔着坏格的两格连边，用例 n = 1, m = 3, broken = [[0,1]] 会错误地返回 1。

错误写法：broken 为空时未初始化 bad 矩阵就直接使用 → Java 中布尔数组默认全 false 无碍，Go 中 make 同样为零值，但若改用哈希集合且忘记初始化，会在查询时空指针。

错误写法：递归函数忘记在遍历完所有邻居后返回 false → 用例中函数返回默认值，Java 编译报错，Go 中同样编译不过；若改成默认返回 true，匹配数会被虚增到左部点数。

相似题目

题目	难度	考察点
785. 判断二分图	中等	只判定二分性本身，用染色 BFS/DFS，是本题建模第一步的独立练习
886. 可能的二分法	中等	由「互相讨厌」的约束建图后做二染色，考的是把关系翻译成边
698. 划分为k个相等的子集	中等	同为「元素不可重复使用」的分组问题，但用回溯加剪枝或状压 DP 求解
473. 火柴拼正方形	中等	698 的特例，练的是搜索顺序与剪枝而非匹配理论
51. N 皇后	困难	同为棋盘上的互斥摆放，但约束是行列对角线冲突，用回溯而非匹配
847. 访问所有节点的最短路径	困难	点数极小的图上用位掩码表示已访问集合，是本题「规模小可状压」的同类
200. 岛屿数量	中等	网格四方向建图的基础题，重点在连通性而不是配对