gistfile1.txt

import edu.princeton.cs.algs4.WeightedQuickUnionUF;

public class Percolation {

    private final int n;

    private boolean[] blocks;

    private boolean[] checkBlocks;

    private final WeightedQuickUnionUF weightedQuickUnionUF;

    // create n-by-n grid, with all sites blocked
    public Percolation(int n) {
        if (n <= 0) {
            throw new IllegalArgumentException("n is illegal");
        }
        this.n = n;
        weightedQuickUnionUF = new WeightedQuickUnionUF(n * n);
        blocks = new boolean[n * n];
        checkBlocks = new boolean[n * n];
        for (int i = 0; i < n * n; i++) {
            blocks[i] = false;
            checkBlocks[i] = false;
        }
    }

    // open site (row, col) if it is not open already
    public void open(int row, int col) {
        // data structure is the following
        //
        //          col=1   col=2     col=3   col=4   col=5
        //    row=1     0       1         2       3       4
        //    row=2     5       6         7       8       9
        //    row=3    10      11        12      13      14
        //    ...
        // if row=2 and col=3, blockIndex=7
        int blockIndex = (row - 1) * n + (col - 1);
//        if(blocks[blockIndex]) {
//            return;
//        }
        // true is open
        blocks[blockIndex] = true;
        //if blockIndex is 7 and upper 2 is open, union(7,2)
        if (row - 2 >= 0 && blocks[(row - 2) * n + (col - 1)]) {
            weightedQuickUnionUF.union(blockIndex, (row - 2) * n + (col - 1));
        }
        //down
        if (row < n && blocks[(row) * n + (col - 1)]) {
            weightedQuickUnionUF.union(blockIndex, (row) * n + (col - 1));
        }
        //left
        if (col - 2 >= 0 && blocks[(row - 1) * n + (col - 2)]) {
            weightedQuickUnionUF.union(blockIndex, (row - 1) * n + (col - 2));
        }
        //right
        if (col < n && blocks[(row - 1) * n + (col)]) {
            weightedQuickUnionUF.union(blockIndex, (row - 1) * n + (col));
        }

    }

    // is site (row, col) open?
    public boolean isOpen(int row, int col) {
        return blocks[(row - 1) * n + (col - 1)];
    }

    // is site (row, col) full?
    public boolean isFull(int row, int col) {
        if (row == 1) {
            return isOpen(row, col);
        }
        //up
        if (row >= 2 && weightedQuickUnionUF.connected((row - 1) * n + (col - 1), (row - 2) * n + (col - 1))) {
            if (isFull(row - 1, col)) {
                return true;
            } else {
                checkBlocks[(row - 2) * n + (col - 1)] = true;
            }
        }

        //down
//        if(row < n && weightedQuickUnionUF.connected((row-1)*n + (col-1), (row)*n + (col-1))) {
//            if(isFull(row+1, col)) {
//                return true;
//            }
//        }

        //left
        if (col >= 2 && weightedQuickUnionUF.connected((row - 1) * n + (col - 1), (row - 1) * n + (col - 2))) {
            checkBlocks[(row - 1) * n + (col - 2)] = true;
            if (isFull(row, col - 1)) {
                return true;
            }
        }

        //right
        if (!checkBlocks[(row - 1) * n + (col - 1)] && col < n && weightedQuickUnionUF.connected((row - 1) * n + (col - 1), (row - 1) * n + (col))) {
            if (isFull(row, col + 1)) {
                return true;
            }
        }
        return false;
    }

    // number of open sites
    public int numberOfOpenSites() {
        int cnt = 0;
        for (int i = 0; i < n * n; i++) {
            if (blocks[i]) {
                cnt++;
            }
        }
        return cnt;
    }

    // does the system percolate?
    public boolean percolates() {
        return isFull(n, 1);
    }

    // test client (optional)
    public static void main(String[] args) {
        // no op
    }
}