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

public class PercolationJZU
{
    private static final int closed = -1;
    private int N;
    // faste using struct { id, weight } ?
    private int[] sites;
    private int[] weights;

    public PercolationJZU(int N)
    {
        this.N = N;
        int n = (N*N)+2;
        sites = new int[n];
        weights = new int[n];
        sites[0] = 0;
        weights[0] = N+1;
        sites[n-1] = n-1;
        weights[n-1] = N+1;
        for(int x=1; x<=n-1; x++)
        {
            sites[x] = x;
            weights[x] = closed;
        }
    }

    private int ijToX(int i, int j)
    {
        if(i<1 || j<1 || i>N || j>N)
            throw new java.lang.IndexOutOfBoundsException("check your indexes");
        return ((j-1)*N)+i;
    }

    private boolean isOpen(int x)
    {
        return (weights[x]!=closed);
    }

    private int root(int x)
    {
        while (x != sites[x])
        {
            sites[x] = sites[sites[x]];
            x = sites[x];
        }
        return x;
    }

    private void connect(int i, int j)
    {
        int ri = root(i);
        int rj = root(j);
        if (ri==rj) return;
        if (weights[ri] < weights[rj])
        {
            sites[ri] = rj;
            weights[rj] += weights[ri];
        }
        else
        {
            sites[rj] = ri;
            weights[ri] += weights[rj];
        }

    }

    public void open(int i, int j)
    {
        int x = ijToX(i,j);
        if (isOpen(x)) return;
        weights[x] = 1;
        if (i>1 && isOpen(x-1)) connect(x,x-1);
        if (i<N && isOpen(x+1)) connect(x,x+1);
        if(j==1) {
            connect(x,0);
            if (isOpen(x+N)) connect(x,x+N);
        }
        else if(j==N) {
            connect(x,N*N+1);
            if (isOpen(x-N)) connect(x,x-N);
        } else {
            if (isOpen(x-N)) connect(x,x-N);
            if (isOpen(x+N)) connect(x,x+N);
        }
    }

    public boolean isOpen(int i, int j)
    {
        return isOpen(ijToX(i,j));
    }

    public boolean isFull(int i, int j)
    {
        int x = ijToX(i,j);
        return ((isOpen(x)) && (root(x)==0));
    }

    public boolean percolates()
    {
        return (root(0)==root(N*N+1));
    }
}