diff options
| -rw-r--r-- | Algorithms/Part-I/1-Percolation/Percolation.java | 63 |
1 files changed, 49 insertions, 14 deletions
diff --git a/Algorithms/Part-I/1-Percolation/Percolation.java b/Algorithms/Part-I/1-Percolation/Percolation.java index 8364585..e41d265 100644 --- a/Algorithms/Part-I/1-Percolation/Percolation.java +++ b/Algorithms/Part-I/1-Percolation/Percolation.java @@ -4,14 +4,18 @@ public class Percolation { private int N; private boolean[] opened; - private WeightedQuickUnionUF uf; + // 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; - uf = new WeightedQuickUnionUF(n); + p = new WeightedQuickUnionUF(n); + f = new WeightedQuickUnionUF(n); opened = new boolean[n]; opened[0] = true; opened[n-1] = true; @@ -25,18 +29,49 @@ public class Percolation int x = (i-1)*N+j; if (opened[x]) return; opened[x] = true; - if (j > 1 && opened[x-1]) uf.union(x, x-1); - if (j < N && opened[x+1]) uf.union(x, x+1); - if (i == 1) { - uf.union(0, x); - if (opened[x+N]) uf.union(x, x+N); + // 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); } - else if (i == N) { - uf.union(N*N+1, x); - if (opened[x-N]) uf.union(x, x-N); + // 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 { - if (opened[x-N]) uf.union(x, x-N); - if (opened[x+N]) uf.union(x, x+N); + // 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); + } } } @@ -54,12 +89,12 @@ public class Percolation 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]) && (uf.find(x) == 0)); + return (opened[x] && (f.find(x) == f.find(0))); } // does the system percolate? public boolean percolates() { - return (uf.find(0) == uf.find(N*N+1)); + return (p.find(0) == p.find(N*N+1)); } } |