/* vim: set expandtab tabstop=4 shiftwidth=4 : */

public class Percolation
{
    private int N;
    private boolean[] opened;
    // to implement percolates, uses top and bottom virtual sites
    private WeightedQuickUnionUF p;
    // to implement isFull, uses only top virtual site
    private WeightedQuickUnionUF f;

    // create N-by-N grid, with all sites blocked
    public Percolation(int N)
    {
        this.N = N;
        int n = (N*N)+2;
        p = new WeightedQuickUnionUF(n);
        f = new WeightedQuickUnionUF(n);
        opened = new boolean[n];
        opened[0] = true;
        opened[n-1] = true;
    }

    // open site (row i, column j) if it is not already
    public void open(int i, int j)
    {
        if (i < 1 || j < 1 || i > N || j > N)
            throw new java.lang.IndexOutOfBoundsException("check your indexes");
        int x = (i-1)*N+j;
        if (opened[x]) return;
        opened[x] = true;
        // left
        if (j > 1 && opened[x-1])
        {
            p.union(x, x-1);
            f.union(x, x-1);
        }
        // right
        if (j < N && opened[x+1])
        {
            p.union(x, x+1);
            f.union(x, x+1);
        }
        // virtual top
        if (i == 1) {
            f.union(0, x);
            p.union(0, x);
            if (opened[x+N])
            {
                p.union(x, x+N);
                f.union(x, x+N);
            }
        } else if (i == N) {
            // virtual bottom
            // only connect percolation
            p.union(N*N+1, x);
            if (opened[x-N])
            {
                p.union(x, x-N);
                f.union(x, x-N);
            }
        } else {
            // up
            if (opened[x-N])
            {
                p.union(x, x-N);
                f.union(x, x-N);
            }
            // down
            if (opened[x+N])
            {
                p.union(x, x+N);
                f.union(x, x+N);
            }
        }
    }

    // is site (row i, column j) open?
    public boolean isOpen(int i, int j)
    {
        if (i < 1 || j < 1 || i > N || j > N)
            throw new java.lang.IndexOutOfBoundsException("check your indexes");
        return opened[(i-1)*N+j];
    }

    // is site (row i, column j) full?
    public boolean isFull(int i, int j)
    {
        if (i < 1 || j < 1 || i > N || j > N)
            throw new java.lang.IndexOutOfBoundsException("check your indexes");
        int x = (i-1)*N+j;
        return (opened[x] && (f.find(x) == f.find(0)));
    }

    // does the system percolate?
    public boolean percolates()
    {
        return (p.find(0) == p.find(N*N+1));
    }
}