引言
小鳄鱼爱洗澡（Where is My Water?）是一款经典的物理解谜游戏：玩家通过挖掘泥土、引导水流，帮助小鳄鱼Swampy顺利洗上澡。游戏中每关的目标是使足够的水流到达目标位置。要将关卡求解问题抽象为算法问题，关键在于将管道布局和障碍物建模为图论中的网络流模型。本文将用Java实现基于网络流建模的关卡求解器，讲解Dinic最大流算法与最小割定理，将物理水流问题转化为图论优化问题高效求解。
核心算法设计
1. 关卡图建模
将游戏地图离散化为网格图G=(V,E)：
– 每个网格单元为一个顶点，属性包括：泥土（可挖掘）、岩石（不可通过）、管道（有向边）、水源（超级源点）、目标点（超级汇点）
– 相邻可通网格之间建立边，容量为1（单格单位水流量）或更大（宽管道）
– 水源连接到所有出水网格，容量为INF
– 所有目标网格连接到超级汇点，容量为需求水量
2. Dinic最大流算法
Dinic算法是求解单源单汇最大流问题的高效算法，时间复杂度O(V²E)（一般网络）或O(E√V)（单位容量网络）。核心步骤：
- BFS分层：从源点出发构建层次图，只保留从低到高的边
- DFS阻塞流：在层次图上沿增广路推送流量，直到不存在增广路
- 重复：当BFS无法到达汇点时，当前流即为最大流
3. 最小割与关卡判定
根据最大流最小割定理：最大流值 = 最小割容量。若最大流值 ≥ 目标需水量，则关卡可通关；否则不可通关。最小割集对应的是”最瓶颈”的管道/泥土位置——即关卡的难点所在。
Java实现
import java.util.*;
/**
* 小鳄鱼爱洗澡关卡求解器
* 核心算法：网络流建模 + Dinic最大流 + 最小割分析
*/
public class CrocodileBathSolver {
// ==================== Dinic最大流核心 ====================
static class Edge {
int to; // 目标顶点
int rev; // 反向边索引
int cap; // 剩余容量
Edge(int to, int rev, int cap) {
this.to = to;
this.rev = rev;
this.cap = cap;
}
}
static class Dinic {
int n; // 顶点数
List<Edge>[] graph; // 邻接表
int[] level; // BFS层次
int[] iter; // 当前弧优化
@SuppressWarnings("unchecked")
Dinic(int n) {
this.n = n;
graph = new ArrayList[n];
for (int i = 0; i < n; i++) graph[i] = new ArrayList<>();
level = new int[n];
iter = new int[n];
}
/**
* 添加有向边及其反向边（残量网络）
* @param from 起点
* @param to 终点
* @param cap 容量
*/
void addEdge(int from, int to, int cap) {
graph[from].add(new Edge(to, graph[to].size(), cap));
graph[to].add(new Edge(from, graph[from].size() - 1, 0)); // 反向边初始容量为0
}
/**
* BFS构建层次图
* @param s 源点
* @param t 汇点
* @return 是否可达汇点
*/
boolean bfs(int s, int t) {
Arrays.fill(level, -1);
Queue<Integer> queue = new LinkedList<>();
level[s] = 0;
queue.add(s);
while (!queue.isEmpty()) {
int v = queue.poll();
for (Edge e : graph[v]) {
if (e.cap > 0 && level[e.to] < 0) {
level[e.to] = level[v] + 1;
queue.add(e.to);
}
}
}
return level[t] >= 0;
}
/**
* DFS在层次图上寻找阻塞流
* @param v 当前顶点
* @param t 汇点
* @param f 当前可推送流量
* @return 实际推送流量
*/
int dfs(int v, int t, int f) {
if (v == t) return f;
for (int i = iter[v]; i < graph[v].size(); i++) {
Edge e = graph[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;
graph[e.to].get(e.rev).cap += d;
return d;
}
}
iter[v]++;
}
return 0;
}
/**
* 计算从s到t的最大流
*/
int maxFlow(int s, int t) {
int flow = 0;
final int INF = Integer.MAX_VALUE;
while (bfs(s, t)) {
Arrays.fill(iter, 0);
int f;
while ((f = dfs(s, t, INF)) > 0) {
flow += f;
}
}
return flow;
}
/**
* 获取最小割的S侧顶点（从源点可达）
* 用于分析关卡瓶颈
*/
boolean[] minCutS side(int s) {
boolean[] visited = new boolean[n];
Queue<Integer> queue = new LinkedList<>();
visited[s] = true;
queue.add(s);
while (!queue.isEmpty()) {
int v = queue.poll();
for (Edge e : graph[v]) {
if (e.cap > 0 && !visited[e.to]) {
visited[e.to] = true;
queue.add(e.to);
}
}
}
return visited;
}
}
// ==================== 关卡地图建模 ====================
static class Cell {
int r, c; // 网格坐标
char type; // '.':空地 '#':泥土 'R':岩石 'W':水源 'D':目标 'P':管道
int pipeCap; // 管道容量（宽管道容量>1）
Cell(int r, int c, char type) {
this.r = r; this.c = c; this.type = type;
this.pipeCap = (type == 'P') ? 2 : 1; // 默认管道容量2，普通通道容量1
}
}
private final int rows, cols;
private final Cell[][] grid;
private final List<Cell> waterSources = new ArrayList<>();
private final List<Cell> targets = new ArrayList<>();
public CrocodileBathSolver(char[][] map) {
this.rows = map.length;
this.cols = map[0].length;
this.grid = new Cell[rows][cols];
for (int r = 0; r < rows; r++) {
for (int c = 0; c < cols; c++) {
grid[r][c] = new Cell(r, c, map[r][c]);
if (map[r][c] == 'W') waterSources.add(grid[r][c]);
if (map[r][c] == 'D') targets.add(grid[r][c]);
}
}
}
/**
* 将网格坐标映射为图顶点编号
*/
int nodeId(int r, int c) {
return r * cols + c;
}
/**
* 构建网络流图
* @param dugCells 已挖掘的泥土格子集合（可作为通道）
* @return 包含源点汇点的Dinic实例
*/
Dinic buildFlowNetwork(Set<Integer> dugCells) {
int totalNodes = rows * cols + 2;
int source = rows * cols; // 超级源点
int sink = rows * cols + 1; // 超级汇点
Dinic dinic = new Dinic(totalNodes);
int[] dr = {-1, 1, 0, 0};
int[] dc = {0, 0, -1, 1};
for (int r = 0; r < rows; r++) {
for (int c = 0; c < cols; c++) {
Cell cell = grid[r][c];
int u = nodeId(r, c);
// 岩石不可通过，跳过
if (cell.type == 'R') continue;
// 泥土未挖掘则不可通过
if (cell.type == '#' && !dugCells.contains(u)) continue;
// 水源连接到超级源点
if (cell.type == 'W') {
dinic.addEdge(source, u, Integer.MAX_VALUE / 4);
}
// 目标点连接到超级汇点（需求水量设为3）
if (cell.type == 'D') {
dinic.addEdge(u, sink, 3);
}
// 四连通邻接
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) continue;
Cell neighbor = grid[nr][nc];
int v = nodeId(nr, nc);
if (neighbor.type == 'R') continue;
if (neighbor.type == '#' && !dugCells.contains(v)) continue;
// 边容量取决于管道类型或默认1
int cap = Math.min(cell.pipeCap, neighbor.pipeCap);
if (cell.type == 'P' || neighbor.type == 'P') {
cap = Math.max(cap, 2);
}
dinic.addEdge(u, v, cap);
}
}
}
return dinic;
}
/**
* 求解当前关卡：计算最大可到达目标的水量
* @param dugCells 已挖掘格子
* @return 最大流值（即可送达目标的水量）
*/
public int solveLevel(Set<Integer> dugCells) {
if (waterSources.isEmpty() || targets.isEmpty()) return 0;
int source = rows * cols;
int sink = rows * cols + 1;
Dinic dinic = buildFlowNetwork(dugCells);
return dinic.maxFlow(source, sink);
}
/**
* 关卡可行性判定与瓶颈分析
* @param requiredWater 通关所需水量
* @param dugCells 已挖掘格子
* @return 分析结果
*/
public LevelAnalysis analyzeLevel(int requiredWater, Set<Integer> dugCells) {
int source = rows * cols;
int sink = rows * cols + 1;
Dinic dinic = buildFlowNetwork(dugCells);
int maxFlow = dinic.maxFlow(source, sink);
boolean canComplete = maxFlow >= requiredWater;
// 最小割分析：找到瓶颈位置
boolean[] sSide = dinic.minCutS side(source);
List<Cell> bottlenecks = new ArrayList<>();
int[] dr = {-1, 1, 0, 0};
int[] dc = {0, 0, -1, 1};
for (int r = 0; r < rows; r++) {
for (int c = 0; c < cols; c++) {
int u = nodeId(r, c);
if (!sSide[u]) continue;
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) continue;
int v = nodeId(nr, nc);
// S侧到T侧的边即为割边
if (!sSide[v] && grid[r][c].type != 'R') {
bottlenecks.add(grid[r][c]);
}
}
}
}
return new LevelAnalysis(maxFlow, requiredWater, canComplete, bottlenecks);
}
static class LevelAnalysis {
int maxFlow;
int requiredWater;
boolean canComplete;
List<Cell> bottlenecks;
LevelAnalysis(int maxFlow, int requiredWater, boolean canComplete, List<Cell> bottlenecks) {
this.maxFlow = maxFlow;
this.requiredWater = requiredWater;
this.canComplete = canComplete;
this.bottlenecks = bottlenecks;
}
}
// ==================== 主程序与测试 ====================
public static void main(String[] args) {
// 定义一个简单关卡地图
// .:空地 #:泥土 R:岩石 W:水源 D:目标 P:管道
char[][] map = {
{'#', '#', '#', '#', '#', '#'},
{'#', 'W', '.', 'P', '.', '#'},
{'#', '#', '#', '.', '#', '#'},
{'#', '.', 'P', '.', 'D', '#'},
{'#', '#', '#', '#', '#', '#'},
};
CrocodileBathSolver solver = new CrocodileBathSolver(map);
System.out.println("===== 小鳄鱼爱洗澡关卡求解器 =====\n");
System.out.println("关卡地图：");
for (char[] row : map) {
System.out.println(" " + new String(row));
}
System.out.println();
// 场景1：未挖掘任何泥土
Set<Integer> noDig = new HashSet<>();
int flow1 = solver.solveLevel(noDig);
System.out.println("场景1（未挖掘）: 最大可送达水量 = " + flow1);
// 场景2：挖通关键泥土格子 (2,3) 和 (2,1)
Set<Integer> digKey = new HashSet<>();
digKey.add(solver.nodeId(2, 3)); // 中间通道
digKey.add(solver.nodeId(2, 1)); // 左侧通道（可选）
int flow2 = solver.solveLevel(digKey);
System.out.println("场景2（挖通关键路径）: 最大可送达水量 = " + flow2);
// 关卡分析
LevelAnalysis analysis = solver.analyzeLevel(3, digKey);
System.out.println("\n关卡分析报告:");
System.out.println(" 最大流/需求量: " + analysis.maxFlow + "/" + analysis.requiredWater);
System.out.println(" 是否可通关: " + (analysis.canComplete ? "是" : "否"));
System.out.println(" 瓶颈位置数: " + analysis.bottlenecks.size());
for (Cell b : analysis.bottlenecks) {
System.out.println(" -> (" + b.r + "," + b.c + ") 类型=" + b.type);
}
}
}
复杂度分析
| 操作 | 时间复杂度 | 空间复杂度 | 说明 |
|---|---|---|---|
| 建图 | O(R×C) | O(R×C) | R行C列网格 |
| Dinic BFS分层 | O(V+E) | O(V) | V≈R×C, E≈4R×C |
| Dinic DFS阻塞流 | O(E×f) | O(V) | f为单位容量下的流量 |
| 整体最大流 | O(V²E) | O(V+E) | 一般网络最坏情况 |
| 最小割分析 | O(V+E) | O(V) | 一次BFS遍历残量网络 |
算法扩展思路
- 多源多汇扩展：引入超级源点和超级汇点后，Dinic天然支持多水源和多目标点的场景，可扩展至复杂管网设计。
- 最小费用最大流：若挖掘不同泥土有不同成本，可为边赋予费用，使用最小费用最大流算法寻找成本最低的通关方案。
- 时变水流模拟：将网络流扩展为时间扩展网络（Time-Expanded Network），模拟水流的动态传播过程，更贴合真实物理。
总结
本文将小鳄鱼爱洗澡的关卡求解问题抽象为网络流模型，通过Dinic算法高效计算最大可送达水量，并利用最大流最小割定理定位关卡瓶颈。该框架展示了如何将物理直觉问题转化为严谨的图论优化问题，是算法在游戏关卡设计与自动测试中的典型应用。
