Last active
February 16, 2017 12:38
-
-
Save mrleolink/919498ec4a5675471f1c696b72d476be to your computer and use it in GitHub Desktop.
My implementation of the union-find assignment at: http://coursera.cs.princeton.edu/algs4/assignments/percolation.html. This implementation includes handling backwash with only ONE union-find object and one extra integer array of size n*n to save status of components.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| import edu.princeton.cs.algs4.WeightedQuickUnionUF; | |
| /** | |
| * Created by leolink on 11/24/16. | |
| */ | |
| public class Percolation { | |
| private static final int UNOPENED = 0b000; | |
| private static final int OPENED = 0b001; | |
| private static final int CONNECTED_TOP = 0b010; | |
| private static final int CONNECTED_BOTTOM = 0b100; | |
| private WeightedQuickUnionUF mWeightedQuickUnionUF; | |
| private int n; | |
| private int[] status; | |
| private boolean percolated; | |
| public Percolation(int n) { | |
| if (n <= 0) throw new IllegalArgumentException(); | |
| this.mWeightedQuickUnionUF = new WeightedQuickUnionUF(n * n); | |
| this.n = n; | |
| this.status = new int[n * n]; // all are UNOPENED | |
| } | |
| public void open(int row, int col) { | |
| checkCornerCase(row, col); | |
| // normalize | |
| row = row - 1; | |
| col = col - 1; | |
| int idx = toIndex(row, col); | |
| // mark as opened | |
| status[idx] |= OPENED; | |
| // union all adjacent cells | |
| // top | |
| if (row == 0) { | |
| status[idx] |= CONNECTED_TOP; | |
| } else { | |
| union(idx, row - 1, col); | |
| } | |
| // bottom | |
| if (row == n - 1) { | |
| status[idx] |= CONNECTED_BOTTOM; | |
| } else { | |
| union(idx, row + 1, col); | |
| } | |
| // left | |
| if (col > 0) { | |
| union(idx, row, col - 1); | |
| } | |
| // right | |
| if (col < n - 1) { | |
| union(idx, row, col + 1); | |
| } | |
| // find common root | |
| int root = mWeightedQuickUnionUF.find(idx); | |
| // root should have same status as idx | |
| status[root] = status[idx]; | |
| // check whether it percolates | |
| if (!percolated) { | |
| boolean connectedTop = (status[idx] & CONNECTED_TOP) == CONNECTED_TOP; | |
| boolean connectedBottom = (status[idx] & CONNECTED_BOTTOM) == CONNECTED_BOTTOM; | |
| percolated = connectedTop && connectedBottom; | |
| } | |
| } | |
| public boolean isOpen(int row, int col) { | |
| checkCornerCase(row, col); | |
| return status[toIndex(row - 1, col - 1)] != UNOPENED; | |
| } | |
| public boolean isFull(int row, int col) { | |
| checkCornerCase(row, col); | |
| // normalize | |
| row = row - 1; | |
| col = col - 1; | |
| // if this cell hasn't been opened, obviously it can't be full | |
| if (status[toIndex(row, col)] == UNOPENED) return false; | |
| // top | |
| if (row == 0) { | |
| return true; | |
| } else { | |
| // return immediately to reduce calls to mWeightedQuickUnionUF | |
| if ((status(row - 1, col) & CONNECTED_TOP) == CONNECTED_TOP) return true; | |
| } | |
| // bottom | |
| if (row < n - 1) { | |
| // return immediately to reduce calls to mWeightedQuickUnionUF | |
| if ((status(row + 1, col) & CONNECTED_TOP) == CONNECTED_TOP) return true; | |
| } | |
| // left | |
| if (col > 0) { | |
| // return immediately to reduce calls to mWeightedQuickUnionUF | |
| if ((status(row, col - 1) & CONNECTED_TOP) == CONNECTED_TOP) return true; | |
| } | |
| // right | |
| if (col < n - 1) { | |
| // return immediately to reduce calls to mWeightedQuickUnionUF | |
| if ((status(row, col + 1) & CONNECTED_TOP) == CONNECTED_TOP) return true; | |
| } | |
| return false; | |
| } | |
| public boolean percolates() { | |
| return percolated; | |
| } | |
| private void checkCornerCase(int... values) { | |
| for (int i : values) { | |
| if (i < 1 || i > n) throw new IndexOutOfBoundsException(); | |
| } | |
| } | |
| /** | |
| * @param row 0-based row | |
| * @param col 0-based col | |
| */ | |
| private int status(int row, int col) { | |
| return status[mWeightedQuickUnionUF.find(toIndex(row, col))]; | |
| } | |
| /** | |
| * @param row 0-based row | |
| * @param col 0-based col | |
| */ | |
| private void union(int idx, int row, int col) { | |
| int adjacent = toIndex(row, col); | |
| if (status[adjacent] != UNOPENED) { | |
| // combine status of the adjacent's root with idx | |
| status[idx] |= status[mWeightedQuickUnionUF.find(adjacent)]; | |
| // actually union idx and adjacent | |
| mWeightedQuickUnionUF.union(idx, adjacent); | |
| } | |
| } | |
| /** | |
| * @param row 0-based row | |
| * @param col 0-based col | |
| */ | |
| private int toIndex(int row, int col) { | |
| return n * row + col; | |
| } | |
| } |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Look luxury boy 🥇 ahii