Visits: 453

Princeton Alhorithms Percolation

普林斯顿大学算法课第 1 次作业“渗透模型 ”。

题目描述： https://coursera.cs.princeton.edu/algs4/assignments/percolation/specification.php

这是一道并查集的问题。

按照题目要求逐步定义 isFull 和 isOpen 是没有难度的，然后只需要在 open 操作中，设置一个 openStatus 为 true 并将它与它周围的四个格子连通即可。

注意 isFull 必须首先满足 isOpen。

这题想要通过，80 分，非常简单，难点在于得高分，因为需要优化的地方非常多，也细节。

首先一个技巧，是 ACM 竞赛中常用的，虚拟起点与虚拟终点，这样可以加速是否连通的判断，不需要遍历整个最后一行，只需要直接看虚拟点是否连接。

由此，我们可以轻松得到 95 分。

但是这样还有 3 个 backwash，分别是 Test Case 16 – 18。

比如一个 3×3 的网格，我们先打开 (1, 1), (1, 2), (1, 3), (2, 3), (3, 3) 和 (3, 1)，由于我们打开到 (3, 3) 的时候，事实上它已经渗透，所以虚拟起点和虚拟终点已经连接，此时我们打开 (3, 1) 之后，它会通过虚拟终点连接到 (3, 3)，并逐步向上直到第一层，最终与虚拟起点连通。这会导致在判断 (3, 1) 的 isFull() 出错。

为此，我们维护另一个并查集，该并查集只有虚拟起点，没有虚拟终点。

以下代码获得 100 分。

</code><code class="java">

import edu.princeton.cs.algs4.WeightedQuickUnionUF;

public class Percolation {

    private final int[][] directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

    // 虚拟起点，减少 UnionFind 的调用
    private static final int TOP = 0;
    private boolean[][] openStatus;
    private final int n;
    private final WeightedQuickUnionUF disjointSet;
    // 为了解决 backwash，这里只用于 TOP 连接
    private final WeightedQuickUnionUF disjointSetBackwash;
    // 虚拟终点，减少 UnionFind 的调用
    private final int bottom;
    // 直接计入 counter，避免 isOpen() 去遍历
    private int counter;

    public Percolation(int n) {
        if (n <= 0) {
            throw new IllegalArgumentException();
        }
        this.n = n;
        openStatus = new boolean[n + 1][n + 1];
        bottom = n * n + 1;
        disjointSet = new WeightedQuickUnionUF(bottom + 1);
        disjointSetBackwash = new WeightedQuickUnionUF(bottom + 1);
    }

    public void open(int row, int col) {
        if (isValid(row, col)) {
            if (!openStatus[row][col]) {
                // 没有打开过才能加 1
                counter++;
                openStatus[row][col] = true;
                // 将第一层与虚拟起点连接，最后一层与虚拟终点连接
                int unionIndex = (row - 1) * n + col;
                if (row == 1) {
                    disjointSet.union(TOP, unionIndex);
                    disjointSetBackwash.union(TOP, unionIndex);
                }
                // 这里不是 else if 因为 n = 1 的时候，头尾都要连通
                if (row == n) {
                    disjointSet.union(bottom, unionIndex);
                    // 不在 backwash 中记录
                }
            }
            for (int[] ints : directions) {
                int newRow = row + ints[0];
                int newCol = col + ints[1];
                if (isValid(newRow, newCol) && isOpen(newRow, newCol)) {
                    int unionIndexP = (row - 1) * n + col;
                    int unionIndexQ = (newRow - 1) * n + newCol;
                    disjointSet.union(unionIndexP, unionIndexQ);
                    disjointSetBackwash.union(unionIndexP, unionIndexQ);
                }
            }
        } else {
            throw new IllegalArgumentException();
        }
    }

    private boolean connectedWithTop(int row, int col) {
        int unionIndex = (row - 1) * n + col;
        return disjointSetBackwash.connected(TOP, unionIndex);
    }

    private boolean isValid(int row, int col) {
        return row >= 1 && row <= n && col >= 1 && col <= n;
    }

    public boolean isOpen(int row, int col) {
        if (isValid(row, col)) {
            return openStatus[row][col];
        } else {
            throw new IllegalArgumentException();
        }
    }

    public boolean isFull(int row, int col) {
        if (isValid(row, col)) {
            // A full site is an open site that can ....
            // 所以 isFull 必须要先满足 isOpen
            return isOpen(row, col) && connectedWithTop(row, col);
        } else {
            throw new IllegalArgumentException();
        }
    }

    public int numberOfOpenSites() {
        return counter;
    }

    public boolean percolates() {
        return disjointSet.connected(TOP, bottom);
    }

    public static void main(String[] args) {
        Percolation p;
        p= new Percolation(2);
        p.open(2, 1);
        p.open(2, 2);
        p.open(1, 2);
        assert p.percolates();

        // Backwash
        // (3, 1) 通过虚拟终点与起点连接，但它其实不是 full 的
        p = new Percolation(3);
        p.open(1, 1);
        p.open(1, 2);
        p.open(1, 3);
        p.open(2, 3);
        p.open(2, 2);
        p.open(3, 3);
        p.open(3, 1);
        assert !p.isFull(3, 1);
        assert p.percolates();
    }

}

import edu.princeton.cs.algs4.StdRandom;
import edu.princeton.cs.algs4.StdStats;

public class PercolationStats {
    private static final double CONFIDENCE = 1.96;
    private final double[] thresholds;
    // 缓存，以减少 Stats 的调用，否则会扣分
    private final double mean;
    private final double stddev;

    public PercolationStats(int n, int trials) {
        if (!isValid(n, trials)) {
            throw new IllegalArgumentException();
        }
        thresholds = new double[trials];
        for (int i = 0; i < trials; ++i) {
          Percolation p = new Percolation(n);
            while (!p.percolates()) {
                int possibleRow = StdRandom.uniform(1, n + 1);
                int possibleCol = StdRandom.uniform(1, n + 1);
                p.open(possibleRow, possibleCol);
            }
            thresholds[i] = (double) (p.numberOfOpenSites()) / (double) (n * n);
        }
        mean = StdStats.mean(thresholds);
        stddev = StdStats.stddev(thresholds);
    }

    private boolean isValid(int n, int trials) {
        return n > 0 && trials > 0;
    }

    public double mean() {
        return mean;
    }

    public double stddev() {
        return stddev;
    }

    public double confidenceLo() {
        return mean - CONFIDENCE * stddev / Math.sqrt(thresholds.length);
    }

    public double confidenceHi() {
        return mean + CONFIDENCE * stddev / Math.sqrt(thresholds.length);
    }

    public static void main(String[] args) {
        int n = Integer.parseInt(args[0]);
        int trials = Integer.parseInt(args[1]);
        PercolationStats ps = new PercolationStats(n, trials);
        System.out.println("mean=" + ps.mean());
        System.out.println("stddev=" + ps.stddev());
        System.out.println("95% confidence interval=[" + ps.confidenceLo() + "," + ps.confidenceHi() + "]");
    }
}