public class Percolation {
	private int size;
	private int count = 0;
	private int head;
	private int tail;
	private boolean[][] opened;
	private WeightedQuickUnionUF uf;
	public Percolation(int n) {
		if (n <= 0)
			throw new IllegalArgumentException();
		size = n;
		uf = new WeightedQuickUnionUF((size + 2) * (size + 2) + 2);
		head = (size + 2) * (size + 2);
		tail = head + 1;
		opened = new boolean[size + 2][size + 2];
		for (int j = 1; j <= size; j++) {
			opened[0][j] = opened[size + 1][j] = true;
			uf.union(head, index(0, j));
			uf.union(tail, index(size + 1, j));
		}
	}
	private int index(int i, int j) {
		return i * (size + 2) + j;
	}
	private boolean valid(int i, int j) {
		return 1 <= i && i <= size && 1 <= j && j <= size;
	}
	public void open(int i, int j) {
		if (!valid(i, j))
			throw new IndexOutOfBoundsException();
		if (!opened[i][j])
			count++;
		opened[i][j] = true;
		if (isOpen(i, j - 1))
			uf.union(index(i, j), index(i, j - 1));
		if (isOpen(i, j + 1))
			uf.union(index(i, j), index(i, j + 1));
		if (isOpen(i - 1, j))
			uf.union(index(i, j), index(i - 1, j));
		if (isOpen(i + 1, j))
			uf.union(index(i, j), index(i + 1, j));
	}
	public boolean isOpen(int i, int j) {
		return opened[i][j];
	}
	public boolean isFull(int i, int j) {
		if (!valid(i, j))
			throw new IndexOutOfBoundsException();
		return uf.connected(head, index(i, j));
	}
	public int numberOfOpenSites() {
		return count;
	}
	public boolean percolates() {
		return uf.connected(head, tail);
	}
}