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
|
/* vim: set expandtab tabstop=4 shiftwidth=4 : */
public class Percolation
{
private int N;
private boolean[] opened;
// 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;
p = new WeightedQuickUnionUF(n);
f = new WeightedQuickUnionUF(n);
opened = new boolean[n];
opened[0] = true;
opened[n-1] = true;
}
// open site (row i, column j) if it is not already
public void open(int i, int j)
{
if (i < 1 || j < 1 || i > N || j > N)
throw new java.lang.IndexOutOfBoundsException("check your indexes");
int x = (i-1)*N+j;
if (opened[x]) return;
opened[x] = true;
// 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);
}
// 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 {
// 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);
}
}
}
// is site (row i, column j) open?
public boolean isOpen(int i, int j)
{
if (i < 1 || j < 1 || i > N || j > N)
throw new java.lang.IndexOutOfBoundsException("check your indexes");
return opened[(i-1)*N+j];
}
// is site (row i, column j) full?
public boolean isFull(int i, int j)
{
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] && (f.find(x) == f.find(0)));
}
// does the system percolate?
public boolean percolates()
{
return (p.find(0) == p.find(N*N+1));
}
}
|
