LeetCode LCP 04. 覆盖
题目描述
题意分析
在有损坏格子的棋盘上放置尽可能多的
1 × 2骨牌，允许横放或竖放。每张骨牌恰好占据两个上下或左右相邻的完好格子，不同骨牌不能共用格子。这相当于从所有相邻格子对中选出尽量多对，同时让每个格子最多属于一对。不能只用完好格子数除以二，因为损坏格子可能切断必要的相邻关系。
解法：二分图最大匹配（匈牙利算法）
核心思路
[!blue]
把每个完好格子作为顶点，两个格子能放一张骨牌时就在它们之间连边。按
(r + c)的奇偶性把格子分为左右两组：相邻格子只改变一个坐标一单位，奇偶性必然相反，所以每条边都连接两组，得到二分图。这里的“左右”只是分组名称，与格子的几何方位无关。一组端点互不重复的边就是一个匹配，对应一组不重叠的骨牌；任意合法骨牌摆法也能反过来得到这样的匹配。因此最多骨牌数恰好等于这张二分图的最大匹配数。
leftId、rightId给两组完好格子分别编号，未分到该组的位置保留-1，避免与合法编号零混淆。adj[u]保存左侧点u可以连接的右侧点，matchRight[v]表示右侧点v当前配给哪个左侧点，-1表示尚未匹配。为一个新的左侧点
u寻找位置时，依次尝试它的邻居v。若v空闲，直接配给u；若已被其他左侧点占用，就递归尝试让原主人改配其他右侧点。只有原主人成功腾出位置，才把matchRight[v]改为u。沿成功链回溯后，每个旧主人仍有配对，新点也得到配对，匹配数恰好增加一；失败时不改写匹配关系。这种沿未匹配边前进、沿已有匹配寻找原主人的链称为增广路径。
seen[v]记录本次搜索已经尝试的右侧点，防止在交替关系中重复绕回；下一次处理新的左侧点时必须重建seen，因为已有匹配可能重新安排，之前尝试过的位置仍有利用价值。若还有更大的匹配，把它与当前匹配不同的边放在一起，会形成交替路径或环；更大匹配多出的边必然落在一条能让当前匹配增加一条边的路径上。因此没有增广路径就意味着已经最大。代码逐个加入左侧点：旧点上的匹配已最大，新增一个左侧点最多使答案增加一，只需从它出发寻找一次增广路径，就能保持当前已处理部分的最大性。
解题步骤
- 标记损坏格子，按奇偶为完好格子分组编号。
- 从一侧向另一侧建立相邻关系。
- 为每个左侧点重新建立访问标记并尝试增广。
- 返回成功增广的次数。
损坏格子既不编号也不连边；搜索四邻居时先检查坐标范围，再检查是否完好。孤立格子没有可选边，它的搜索失败不会影响其他格子；所有格子损坏或没有任何相邻完好格子时，没有成功增广，答案自然为零。
代码实现
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
}
复杂度分析
- 时间复杂度：设棋盘格数为 G、左右点数为 L、R、边数为 E，包含初始化的上界为 $O(G+L(R+E))$。
- 空间复杂度：$O(G+E)$，包括格子编号、邻接表、匹配和本次访问记录。
关键点总结
[!green]
- 匹配边与合法骨牌一一对应。
- 增广允许重新安排已有配对，不是只找当前空位。
- 每次尝试的访问记录重新开始，已有匹配继续保留。
易错点总结
[!yellow]
- 使用行号奇偶染色：同一行相邻格子没有被分到两侧。
- 找到邻居已占用就立即放弃：可能通过增广重新安排。
- 匹配尚未确认成功就覆盖旧关系：失败时会破坏已有配对。
- 按完好格子数直接除以二：完好格子未必存在足够的相邻关系。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 1349. 参加考试的最大学生数 | 困难 | 都可建二分图，但分组与边规则不同；本题求最大匹配数，考试题的最大独立集由顶点数减最大匹配数得到。 |