LCP 04. 覆盖 Java 题解题意分析棋盘是 n * m 网格部分格子被障碍物占用。每次可以放置一张 2×1 多米诺骨牌覆盖相邻两个空白格子上下/左右。求最多能放置多少张骨牌。模型转化二分图最大匹配经典棋盘二分图建模1. 黑白染色像国际象棋棋盘 (ij) 偶数为左集合奇数为右集合2. 相邻可放骨牌 → 黑白格子之间连边3. 障碍物格子不加入图问题等价求二分图最大匹配匹配数就是最多骨牌数量。算法DFS 匈牙利算法二分图最大匹配Java 完整实现javaimport java.util.*;class Solution {// 方向上下左右private final int[][] dirs {{-1,0},{1,0},{0,-1},{0,1}};private int n, m;private int[][] grid;// matchTo[v]右侧点v匹配到左侧哪个点private int[] matchTo;// 访问标记单次dfs防止环private boolean[] vis;public int domino(int n, int m, int[][] broken) {this.n n;this.m m;grid new int[n][m];// 标记障碍1为障碍0空白for (int[] p : broken) {grid[p[0]][p[1]] 1;}// 给右侧黑色格子编号int id 0;int[][] rightId new int[n][m];for (int i 0; i n; i) {Arrays.fill(rightId[i], -1);for (int j 0; j m; j) {if (grid[i][j] 0 (i j) % 2 1) {rightId[i][j] id;}}}matchTo new int[id];Arrays.fill(matchTo, -1);int res 0;// 遍历左侧点 (ij) 偶数for (int i 0; i n; i) {for (int j 0; j m; j) {if (grid[i][j] 0 (i j) % 2 0) {vis new boolean[id];if (dfs(i, j, rightId)) {res;}}}}return res;}// 左侧点(i,j)尝试找增广路private boolean dfs(int x, int y, int[][] rightId) {for (int[] d : dirs) {int nx x d[0];int ny y d[1];if (nx 0 || nx n || ny 0 || ny m) continue;if (grid[nx][ny] 1) continue;int rid rightId[nx][ny];if (rid -1 || vis[rid]) continue;vis[rid] true;// 未匹配 或 匹配的左侧点可以重新找到其他右侧点if (matchTo[rid] -1 || dfs(matchTo[rid] / m, matchTo[rid] % m, rightId)) {matchTo[rid] x * m y;return true;}}return false;}}核心思路拆解1. 棋盘二分染色(ij) % 2 0 左部节点 (ij)%21 右部节点。骨牌一定横跨黑白两点。2. 右侧节点离散编号给所有可通行的黑色格子分配唯一 id用于 matchTo 数组。3. 匈牙利 DFS 增广- 遍历左侧每个空白白点- 向四周合法黑点发起匹配- 黑点未匹配 → 直接匹配成功- 已匹配 → 递归给原来匹配的白点重新找新黑点能找到则抢占。4. 最终匹配数量 最多骨牌数。复杂度分析设空白格子总数为 V相邻边数 E。- 时间O(V\cdot E)小规模棋盘题目可通过- 空间O(nm) 存储编号、匹配数组。优化可选BFS 匈牙利 / Dinic 网络最大流当棋盘尺寸极大DFS 容易超时可1. 将二分图转为源点→左集合→右集合→汇点的流量网络2. 边容量均为 1Dinic 求最大流结果等价最大匹配。测试样例示例示例 1plaintextn2,m2,broken[[1,1]]棋盘0 00 障碍最多骨牌1输出 1关键点避坑1. 障碍物格子直接跳过不建边2. 每次 DFS 重置 vis 数组避免单次搜索重复访问右侧节点3. 右侧编号必须只给 (ij)%21 空白格否则索引越界。需要我提供 Dinic 网络流优化版本、Python / Go 实现可以直接说明。