Kimi LeetCode LCP 38. 守卫城堡 Java实现

LCP 38. 守卫城堡 - Java 实现题目概述2 \times N 的方格图包含平地 .、障碍物 #、出生点 S、瞬移点 P、城堡 C。玩家可在平地上放置障碍物. 变 #求最少放置多少个障碍物使恶魔无法从任意 S 到达 C。若不可能则返回 -1。核心思路最小割建模本题本质是最小点割集问题转化为网络最大流 / 最小割求解。建图规则操作 容量 含义每个格子拆点入点 → 出点 . 为 1S/P/C 为 INF 在平地放障碍代价为 1特殊点不可放相邻格子出点 → 邻居入点 INF 恶魔可自由移动所有 P 点连超级 P 节点 INF 瞬移功能超级源点 → 所有 S 入点 INF 恶魔出生点C 出点 → 超级汇点 INF 城堡为终点跑 Dinic 最大流 最小割。若最小割 \ge INF说明必须切断特殊点返回 -1。---Java 代码javaimport java.util.*;class Solution {public int guardCastle(String[] grid) {int rows grid.length;int cols grid[0].length();int n rows * cols;final int INF (int) 1e9;// 节点编号入点 [0, n-1]出点 [n, 2n-1]int SRC 2 * n; // 超级源点int SNK 2 * n 1; // 超级汇点int PNODE 2 * n 2; // 超级 P 节点瞬移中转Dinic dinic new Dinic(2 * n 3);int[] dr {-1, 1, 0, 0};int[] dc {0, 0, -1, 1};Listint[] sPoints new ArrayList();int[] cPoint null;// 收集特殊点for (int r 0; r rows; r) {for (int c 0; c cols; c) {char ch grid[r].charAt(c);if (ch S) sPoints.add(new int[]{r, c});else if (ch C) cPoint new int[]{r, c};}}// 没有恶魔或没有城堡无需防御if (sPoints.isEmpty() || cPoint null) return 0;// 建图for (int r 0; r rows; r) {for (int c 0; c cols; c) {char ch grid[r].charAt(c);if (ch #) continue; // 障碍物不可通行int inNode r * cols c;int outNode inNode n;// 拆点入点 - 出点容量为放置障碍物的代价int cost (ch .) ? 1 : INF;dinic.addEdge(inNode, outNode, cost);// 相邻格子连边出点 - 邻居入点for (int d 0; d 4; d) {int nr r dr[d], nc c dc[d];if (nr 0 nr rows nc 0 nc cols grid[nr].charAt(nc) ! #) {int nInNode nr * cols nc;dinic.addEdge(outNode, nInNode, INF);}}// P 点瞬移入点 - 超级P - 出点if (ch P) {dinic.addEdge(inNode, PNODE, INF);dinic.addEdge(PNODE, outNode, INF);}}}// 源点连接所有 Sfor (int[] sp : sPoints) {dinic.addEdge(SRC, sp[0] * cols sp[1], INF);}// C 连接汇点dinic.addEdge(cPoint[0] * cols cPoint[1] n, SNK, INF);int res dinic.maxFlow(SRC, SNK);return res INF ? -1 : res;}}// Dinic 最大流模板class Dinic {static class Edge {int to, rev, cap;Edge(int to, int rev, int cap) {this.to to; this.rev rev; this.cap cap;}}ListEdge[] g;int[] level, iter;int n;Dinic(int n) {this.n n;g new ArrayList[n];for (int i 0; i n; i) g[i] new ArrayList();level new int[n];iter new int[n];}void addEdge(int from, int to, int cap) {g[from].add(new Edge(to, g[to].size(), cap));g[to].add(new Edge(from, g[from].size() - 1, 0));}void bfs(int s) {Arrays.fill(level, -1);QueueInteger q new LinkedList();level[s] 0;q.add(s);while (!q.isEmpty()) {int v q.poll();for (Edge e : g[v]) {if (e.cap 0 level[e.to] 0) {level[e.to] level[v] 1;q.add(e.to);}}}}int dfs(int v, int t, int f) {if (v t) return f;for (int i iter[v]; i g[v].size(); i) {iter[v] i;Edge e g[v].get(i);if (e.cap 0 level[v] level[e.to]) {int d dfs(e.to, t, Math.min(f, e.cap));if (d 0) {e.cap - d;g[e.to].get(e.rev).cap d;return d;}}}return 0;}int maxFlow(int s, int t) {int flow 0;final int INF_FLOW (int) 1e9;while (true) {bfs(s);if (level[t] 0) return flow;Arrays.fill(iter, 0);int f;while ((f dfs(s, t, INF_FLOW)) 0) flow f;}}}---复杂度分析指标 复杂度 说明时间 O(V^2 \cdot E) 实际接近 O(E \cdot \sqrt{V}) Dinic 算法V \le 4 \times 10^4 3E \le 2 \times 10^5空间 O(V E) 邻接表存图关键点说明- 拆点技巧将点权放障碍物的代价转化为边权这是最小割求最小点割的标准做法。- P 点处理所有 P 共享一个超级节点实现到达任意 P 即可瞬移到任意 P的语义。- INF 边相邻移动、瞬移、源点/汇点连接的边容量设为 INF确保最小割只会选择代价为 1 的平地边。- 无解判断若最小割 \ge INF说明必须切断 S/P/C 等特殊点返回 -1。