渗流阈值计算结果偏高0.1，Java代码排查无果求助

核心错误分析 #

你的代码中渗流检测逻辑不符合定义，这是导致阈值偏高（0.7而非预期0.6）的根本原因：

• 原代码的isNaivePercolation(int n)仅验证**刚涂黑的单元格n**是否同时连通顶部行和底部行，但渗流的正确定义是：网格中存在任意顶部行的黑色单元格到任意底部行的黑色单元格的连通路径，无论该路径是否包含新涂黑的单元格。
• 这种错误会导致：即使网格中已经形成了符合要求的连通路径，只要新涂黑的单元格不在这条路径上，代码就不会检测到渗流，直到后续涂黑的单元格恰好接入这条路径，从而需要更多的黑色单元格，最终阈值被高估。

修复方案 #

方案1：修正递归检测逻辑 #

修改渗流检测方法，遍历所有顶部行的黑色单元格，检查是否存在连通到底部行的路径：

public static boolean isPercolation() {
    boolean[] seen = new boolean[length];
    // 遍历所有顶部行的黑色单元格
    for (int j = 0; j < size; j++) {
        int topIndex = j;
        if (grid[topIndex] && detectPathToBottom(seen, topIndex)) {
            return true;
        }
    }
    return false;
}

private static boolean detectPathToBottom(boolean[] seen, int n) {
    if (n < 0 || n >= length || seen[n] || !grid[n]) {
        return false;
    }
    // 到达底部行，返回true
    if (n >= length - size) {
        return true;
    }
    seen[n] = true;
    int col = n % size;
    // 检查上下左右邻接单元格
    return detectPathToBottom(seen, n - size) ||
           detectPathToBottom(seen, n + size) ||
           (col > 0 && detectPathToBottom(seen, n - 1)) ||
           (col < size - 1 && detectPathToBottom(seen, n + 1));
}

同时更新percolation()方法中的检测逻辑：

public static double percolation() {
    init();
    int blackenedCells = 0;
    int index;
    boolean percolationDetected = false;
    while (!percolationDetected) {
        index = randomShadow();
        blackenedCells++;
        // 调用修正后的检测方法，无需传入新涂黑的单元格索引
        percolationDetected = isPercolation();
    }
    print();
    return (double) blackenedCells / length;
}

方案2：使用并查集（Union-Find）数据结构（更高效） #

对于较大的网格，递归DFS可能存在栈溢出问题，且效率较低。并查集是解决渗流问题的经典数据结构，能高效跟踪单元格的连通性：

public class Percolation {
    public static final int size = 10;
    public static final int length = size * size;
    public static boolean[] grid = new boolean[length];
    // 并查集数组，额外添加两个虚拟节点：顶部虚拟节点（length）、底部虚拟节点（length+1）
    private static int[] parent = new int[length + 2];
    private static int[] rank = new int[length + 2];

    public static void init() {
        for (int i = 0; i < length; i++) {
            grid[i] = false;
        }
        // 初始化并查集
        for (int i = 0; i < parent.length; i++) {
            parent[i] = i;
            rank[i] = 1;
        }
        // 将顶部行所有单元格与顶部虚拟节点连通
        for (int j = 0; j < size; j++) {
            union(j, length);
        }
        // 将底部行所有单元格与底部虚拟节点连通
        for (int j = 0; j < size; j++) {
            union(length - size + j, length + 1);
        }
    }

    // 并查集查找方法（带路径压缩）
    private static int find(int x) {
        if (parent[x] != x) {
            parent[x] = find(parent[x]);
        }
        return parent[x];
    }

    // 并查集合并方法（按秩合并）
    private static void union(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);
        if (rootX == rootY) return;
        if (rank[rootX] < rank[rootY]) {
            parent[rootX] = rootY;
        } else {
            parent[rootY] = rootX;
            if (rank[rootX] == rank[rootY]) {
                rank[rootX]++;
            }
        }
    }

    public static int randomShadow() {
        int index;
        do {
            index = (int) (Math.random() * length);
        } while (grid[index]);
        grid[index] = true;
        // 将当前涂黑的单元格与上下左右的黑色单元格连通
        int col = index % size;
        // 上方单元格
        if (index >= size && grid[index - size]) {
            union(index, index - size);
        }
        // 下方单元格
        if (index < length - size && grid[index + size]) {
            union(index, index + size);
        }
        // 左方单元格
        if (col > 0 && grid[index - 1]) {
            union(index, index - 1);
        }
        // 右方单元格
        if (col < size - 1 && grid[index + 1]) {
            union(index, index + 1);
        }
        return index;
    }

    public static boolean isPercolation() {
        // 若顶部虚拟节点与底部虚拟节点连通，则存在渗流路径
        return find(length) == find(length + 1);
    }

    // 保留原有的print()、percolation()、main()方法，仅修改percolation()中的检测逻辑
    public static double percolation() {
        init();
        int blackenedCells = 0;
        int index;
        boolean percolationDetected = false;
        while (!percolationDetected) {
            index = randomShadow();
            blackenedCells++;
            percolationDetected = isPercolation();
        }
        print();
        return (double) blackenedCells / length;
    }

    // 原print()方法不变
    public static void print() {
        for (int i = 0; i < size; i++) {
            for (int j = 0; j < size; j++) {
                int index = i * size + j;
                if (grid[index]) {
                    System.out.print("*");
                } else {
                    System.out.print("-");
                }
            }
            System.out.println();
        }
    }

    public static void main(String[] args) {
        init();
        System.out.println("Matrix after initializing:");
        print();
        System.out.println();

        int blackenedIndex = randomShadow();
        System.out.println("Matrix after blackening a random cell:");
        print();
        System.out.println("Index of blackened cell: " + blackenedIndex);
        System.out.println();

        System.out.println("Testing percolation:");
        double percolationThreshold = percolation();
        System.out.println("Percolation threshold: " + percolationThreshold);
    }
}

验证说明 #

修正后，代码会正确检测网格中是否存在任意顶部到底部的黑色连通路径，多次运行后阈值会接近预期的0.6左右。此外，使用并查集的方案不仅更高效，也避免了递归DFS的栈溢出风险，适合更大规模的网格测试。

内容的提问来源于stack exchange，提问作者Perseus