Percolation(渗滤)

  1public class Percolation {
  2
  3    private int size;
  4    private WeightedQuickUnionUF grid ;
  5    private int openCount;
  6    private boolean[] openFlag;
  7    private int vTop;
  8    private int vBottom;
  9
 10    // creates n-by-n grid, with all sites initially blocked
 11    public Percolation(int n) {
 12        if (n <= 0)
 13            throw new IllegalArgumentException();
 14        this.size = n;
 15        // n^2 + 2 virtual sites
 16        // assume the last 2 sites are VTop and vBottom
 17        // 0 ~ (n^2 - 1)
 18        grid = new WeightedQuickUnionUF(n * n + 2);
 19        vTop = n * n ;
 20        vBottom = n * n + 1;
 21        // init all sites closed
 22        openFlag = new boolean[n * n];
 23        for (int i = 0; i < n * n; i++) {
 24            openFlag[i] = false;
 25        }
 26    }
 27
 28    private void validate(int row, int col){
 29        if (row < 1 || row > size || col < 1 || col > size)
 30            throw new IllegalArgumentException();
 31    }
 32
 33    // check site adjacent sites
 34    private boolean validate(int rl) {
 35        return rl >= 1 && rl <= size;
 36    }
 37
 38    private int calIndex(int row, int col){
 39        validate(row, col);
 40        // start from 0
 41        return size * (row - 1) + col - 1;
 42    }
 43
 44
 45    // opens the site (row, col) if it is not open already
 46    public void open(int row, int col) {
 47        if (isOpen(row, col)) return;
 48        int p = calIndex(row, col);
 49        if (row == 1) {
 50            // connect to vTop
 51            grid.union(p, vTop);
 52        }
 53        if (row == size) {
 54            // connect to vBottom
 55            grid.union(p, vBottom);
 56        }
 57        // connect adjacent open site
 58        // up
 59        if (validate(row - 1) && isOpen(row - 1, col)) 
 60            grid.union(p, calIndex(row - 1, col));
 61        // right
 62        if (validate(col + 1) && isOpen(row, col + 1))
 63            grid.union(p, calIndex(row, col + 1 ));
 64        // bottom
 65        if (validate(row + 1) && isOpen(row + 1, col))
 66            grid.union(p, calIndex(row + 1, col));
 67        // left
 68        if (validate(col - 1) && isOpen(row, col - 1))
 69            grid.union(p, calIndex(row, col - 1));
 70
 71        openFlag[p] = true;
 72        openCount++;
 73    }
 74
 75    // is the site (row, col) open?
 76    public boolean isOpen(int row, int col) {
 77        int p = calIndex(row, col);
 78        return openFlag[p];
 79    }
 80
 81    // is the site (row, col) full?
 82    // iff the site is connected to Top row open site
 83    public boolean isFull(int row, int col) {
 84        int p = calIndex(row, col);
 85        if (!openFlag[p]) return false;
 86        // is this correct?
 87        return grid.find(p) == grid.find(vTop);
 88    }
 89
 90    // returns the number of open sites
 91    public int numberOfOpenSites() {
 92        return openCount;
 93    }
 94
 95    // does the system percolate?
 96    // iff any bottom row site if full
 97    public boolean percolates() {
 98        return grid.find(vTop) == grid.find(vBottom);
 99    }
100
101    // test client (optional)
102    public static void main(String[] args) {
103        // corner cases tests
104        // case0 N = 0
105        // Percolation p0 = new Percolation(0);
106        // case1: N = 1
107        Percolation p1 = new Percolation(1);
108        StdOut.println("n = 1, percolates? " + p1.percolates());
109        p1.open(1, 1);
110        StdOut.println("n = 1, percolates? " + p1.percolates());
111        // case2: N = 5
112        Percolation p2 = new Percolation(5);
113        p2.open(3,4);
114        p2.open(1,2);
115        p2.open(2,3);
116        p2.open(4,3);
117        p2.open(5,3);
118        p2.open(3,3);
119        p2.open(1,3);
120        StdOut.println("n = 5, openCount " + p2.openCount);
121        StdOut.println("percolates? " + p2.percolates());
122        StdOut.println("full? " + p2.isFull(4,2));
123    }
124}