1 public class Percolation {  2     private boolean[] openSites;  3     private int gridN;  4     private WeightedQuickUnionUF UF;  5     private WeightedQuickUnionUF UFfull;  6   7     public Percolation(int N) {  8         if (N <= 0) {  9             throw new java.lang.IllegalArgumentException( 10             "N must be greater than 0"); 11         } 12         openSites = new boolean[N * N]; 13         gridN = N; 14         for (int i = 0; i < N * N; ++i) { 15             openSites[i] = false; 16         } 17         // add 2 virtual sites 18         UF = new WeightedQuickUnionUF(N * N + 2); 19         UFfull = new WeightedQuickUnionUF(N * N + 1); 20     } 21  22     private void indexChecker(int i, int j) { 23         if (i < 1 || j < 1 || i > gridN || j > gridN) 24             throw new java.lang.IndexOutOfBoundsException(); 25     } 26  27     public void open(int i, int j) { 28         indexChecker(i, j); 29  30         int indexI = i - 1; 31         int indexJ = j - 1; 32  33         int osIndex = indexI * gridN + indexJ; 34         if (openSites[osIndex]) 35             return; 36         openSites[osIndex] = true; 37  38         int ufIndex = indexI * gridN + indexJ + 1; 39         if (indexI == 0) { 40             UF.union(0, ufIndex); 41             UFfull.union(0, ufIndex); 42         } 43         if (indexI == gridN - 1) { 44             UF.union(ufIndex, gridN * gridN + 1); 45         } 46  47         boolean bOpen = false; 48  49         // union adjacent open sites 50         int leftIndexI = indexI; 51         int leftIndexJ = indexJ - 1; 52         if (leftIndexJ >= 0) { 53             bOpen = isOpen(leftIndexI + 1, leftIndexJ + 1); 54             if (bOpen) { 55                 int leftUFIndex = leftIndexI * gridN + leftIndexJ + 1; 56                 UF.union(leftUFIndex, ufIndex); 57                 UFfull.union(leftUFIndex, ufIndex); 58             } 59         } 60  61         int rightIndexI = indexI; 62         int rightIndexJ = indexJ + 1; 63         if (rightIndexJ < gridN) { 64             bOpen = isOpen(rightIndexI + 1, rightIndexJ + 1); 65             if (bOpen) { 66                 int rightUFIndex = rightIndexI * gridN + rightIndexJ + 1; 67                 UF.union(ufIndex, rightUFIndex); 68                 UFfull.union(ufIndex, rightUFIndex); 69             } 70         } 71  72         int upIndexI = indexI - 1; 73         int upIndexJ = indexJ; 74         if (upIndexI >= 0) { 75             bOpen = isOpen(upIndexI + 1, upIndexJ + 1); 76             if (bOpen) { 77                 int upUFIndex = upIndexI * gridN + upIndexJ + 1; 78                 UF.union(upUFIndex, ufIndex); 79                 UFfull.union(upUFIndex, ufIndex); 80             } 81         } 82  83         int downIndexI = indexI + 1; 84         int downIndexJ = indexJ; 85         if (downIndexI < gridN) { 86             bOpen = isOpen(downIndexI + 1, downIndexJ + 1); 87             if (bOpen) { 88                 int downUFIndex = downIndexI * gridN + downIndexJ + 1; 89                 UF.union(ufIndex, downUFIndex); 90                 UFfull.union(ufIndex, downUFIndex); 91             } 92         } 93     } 94  95     public boolean isOpen(int i, int j) { 96         indexChecker(i, j); 97         return (openSites[(i - 1) * gridN + j - 1]); 98     } 99 100     public boolean isFull(int i, int j) {101         indexChecker(i, j);102         int indexI = i - 1;103         int indexJ = j - 1;104 105         int osIndex = indexI * gridN + indexJ;106         int ufIndex = osIndex + 1;107 108         boolean bOpen = isOpen(i, j);109         boolean isFull = UFfull.connected(0, ufIndex);110         return (bOpen && isFull);111     }112 113     public boolean percolates() {114         if (gridN == 1)115             return (openSites[0]);116         return UF.connected(0, gridN * gridN + 1);117     }118 }