-
Notifications
You must be signed in to change notification settings - Fork 0
/
Percolation.java
105 lines (88 loc) · 2.81 KB
/
Percolation.java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
import edu.princeton.cs.algs4.WeightedQuickUnionUF;
public class Percolation {
private boolean[] isOpened;
private WeightedQuickUnionUF uf1;
private WeightedQuickUnionUF uf2;
private int n;
private int openCount;
// creates n-by-n grid, with all sites initially blocked
public Percolation(int n) {
if (n <= 0) {
throw new IllegalArgumentException();
}
isOpened = new boolean[n * n + 2];
openCount = 0;
uf1 = new WeightedQuickUnionUF(n * n + 2);
uf2 = new WeightedQuickUnionUF(n * n + 1);
this.n = n;
}
private int translatePos(int row, int col) {
if (row <= 0 || row > n || col <= 0 || col > n) {
throw new IllegalArgumentException();
}
return (row - 1) * n + col;
}
// opens the site (row, col) if it is not open already
public void open(int row, int col) {
if (isOpen(row, col))
return;
int index = translatePos(row, col);
isOpened[index] = true;
openCount++;
if (row == 1) {
uf1.union(0, index);
uf2.union(0, index);
}
else if (row > 1) {
if (isOpen(row - 1, col)) {
uf1.union(translatePos(row - 1, col), index);
uf2.union(translatePos(row - 1, col), index);
}
}
if (row == n) {
uf1.union(n * n + 1, index);
}
else if (row < n) {
if (isOpen(row + 1, col)) {
uf1.union(translatePos(row + 1, col), index);
uf2.union(translatePos(row + 1, col), index);
}
}
if (col > 1) {
if (isOpen(row, col - 1)) {
uf1.union(translatePos(row, col - 1), index);
uf2.union(translatePos(row, col - 1), index);
}
}
if (col < n) {
if (isOpen(row, col + 1)) {
uf1.union(translatePos(row, col + 1), index);
uf2.union(translatePos(row, col + 1), index);
}
}
}
// is the site (row, col) open?
public boolean isOpen(int row, int col) {
return isOpened[translatePos(row, col)];
}
// Index starts from 1
// is the site (row, col) full?
public boolean isFull(int row, int col) {
int index = translatePos(row, col);
if (isOpen(row, col)) {
return uf2.find(index) == uf2.find(0); // check whether connected to the top
}
return false;
}
// returns the number of open sites
public int numberOfOpenSites() {
return openCount;
}
// does the system percolate?
public boolean percolates() {
return uf1.find(0) == uf1.find(n * n + 1);
}
// test client (optional)
public static void main(String[] args) {
}
}