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() + "]"); } }