PercolationDown.java

Below is the syntax highlighted version of PercolationDown.java from §2.4 Case Study: Percolation.

/*************************************************************************
 *  Compilation:  javac PercolationDown.java
 *  Execution:    java PercolationDown < input.txt
 *
 *  % java PercolationDown < testT.txt
 *  6 6
 *  0 1 1 0 0 0 
 *  0 0 1 1 1 1 
 *  0 0 0 1 1 0 
 *  0 0 0 0 1 1 
 *  0 1 1 1 1 1 
 *  1 1 0 1 0 0 
 *  true
 *
 *  % java PercolationDown < testF.txt
 *  6 6
 *  0 1 0 1 0 0 
 *  1 1 1 0 0 0 
 *  1 0 1 1 0 0 
 *  0 0 0 1 1 1 
 *  0 0 0 0 0 1 
 *  0 0 0 0 0 0 
 *  false
 *
 *************************************************************************/

public class PercolationDown { 

    // given an N-by-N matrix of open sites, return an N-by-N matrix
    // of sites reachable from the top
    public static boolean[][] flow(boolean[][] open) {
        int N = open.length;
        boolean[][] full = new boolean[N][N];
        for (int j = 0; j < N; j++)
            full[0][j] = open[0][j];

        for (int i = 1; i < N; i++) {
            for (int j = 0; j < N; j++) {
                boolean fill = false;
                for (int k = j; (k < N) && open[i][k]; k++)
                    fill = fill || full[i-1][k];
                for (         ; (j < N) && open[i][j]; j++)
                    if (fill) full[i][j] = true;
            }
        }
        return full;
    }

    // does the system percolate down
    public static boolean percolates(boolean[][] open) {
        boolean[][] full = flow(open);
        int N = full.length;
        for (int j = 0; j < N; j++)
            if (full[N-1][j]) return true;
        return false;
    }

    // test client
    public static void main(String[] args) {
        boolean[][] open = BooleanMatrix.read();
        BooleanMatrix.print(flow(open));
        StdOut.println(percolates(open));
    }
}