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
|
/* vim: set expandtab tabstop=4 shiftwidth=4 : */
public class PercolationJZU
{
private static final int closed = -1;
private int N;
// faste using struct { id, weight } ?
private int[] sites;
private int[] weights;
public PercolationJZU(int N)
{
this.N = N;
int n = (N*N)+2;
sites = new int[n];
weights = new int[n];
sites[0] = 0;
weights[0] = N+1;
sites[n-1] = n-1;
weights[n-1] = N+1;
for(int x=1; x<=n-1; x++)
{
sites[x] = x;
weights[x] = closed;
}
}
private int ijToX(int i, int j)
{
if(i<1 || j<1 || i>N || j>N)
throw new java.lang.IndexOutOfBoundsException("check your indexes");
return ((j-1)*N)+i;
}
private boolean isOpen(int x)
{
return (weights[x]!=closed);
}
private int root(int x)
{
while (x != sites[x])
{
sites[x] = sites[sites[x]];
x = sites[x];
}
return x;
}
private void connect(int i, int j)
{
int ri = root(i);
int rj = root(j);
if (ri==rj) return;
if (weights[ri] < weights[rj])
{
sites[ri] = rj;
weights[rj] += weights[ri];
}
else
{
sites[rj] = ri;
weights[ri] += weights[rj];
}
}
public void open(int i, int j)
{
int x = ijToX(i,j);
if (isOpen(x)) return;
weights[x] = 1;
if (i>1 && isOpen(x-1)) connect(x,x-1);
if (i<N && isOpen(x+1)) connect(x,x+1);
if(j==1) {
connect(x,0);
if (isOpen(x+N)) connect(x,x+N);
}
else if(j==N) {
connect(x,N*N+1);
if (isOpen(x-N)) connect(x,x-N);
} else {
if (isOpen(x-N)) connect(x,x-N);
if (isOpen(x+N)) connect(x,x+N);
}
}
public boolean isOpen(int i, int j)
{
return isOpen(ijToX(i,j));
}
public boolean isFull(int i, int j)
{
int x = ijToX(i,j);
return ((isOpen(x)) && (root(x)==0));
}
public boolean percolates()
{
return (root(0)==root(N*N+1));
}
}
|
