最近又回顾了一遍Coursera上的神课，普林斯顿大学教授Robert Sedgewick主讲的Algorithms. Week1中interview questions已经贴出来了，今天给大家分享的是Week1的assignment:Percolation.
链接：课程的Specification
这个作业的目的是通过蒙特卡洛来估算一个由n*n格子组成系统的渗透阈值。
何为渗透
在n*n中，一个格子有三种状态：
（1）开放状态open
（2）堵塞状态blocked
（3）开放且能渗透状态full
从系统顶端能通过开放状态的格子到达系统底端，即为渗透。
何为阈值
假设一个格子开放的概率为p，可知p=0时系统永不渗透，p=1时系统一定渗透。逐渐增加p值，可以获得渗透阈值。
代码部分
可以看出这个问题和老爷子讲的union-find离不开关系，本次作业就是利用Union-find来实现的。
仔细思考过后发现问题其实并不困难，我用了virtualTop和virtualBottoom，将virtualTop和第一行相连通，virtualBottom和最后一行相连通。最后只要判断virtualTop和virtualBottom有没有连通即可。但是跑了测试样例之后发现一个问题，也就是checklist里面提到的backwash。
通过一个WeightedQuickUnionUF似乎不能解决这个问题，因为我用了两个【手动狗头】一个WeightedQuickUnionUF是带有virtualTop和virtualBottom的，另一个只带有virtualTop。判断full的时候利用第二个WeightedQuickUnionUF，判断是否渗透则用第一个。
以下是percolation.java的代码。代码中还需注意的一点是我将virtualTop和virtualBottom分别放在了数组的前两位，这样计算其余格子的索引比较方便。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
81import edu.princeton.cs.algs4.In;
import edu.princeton.cs.algs4.StdDraw;
import edu.princeton.cs.algs4.WeightedQuickUnionUF;
public class Percolation {
private boolean[] map; //用了一维数组，因为相比于二维数组，一维的代码更简洁明了
private WeightedQuickUnionUF union;
private WeightedQuickUnionUF backwash;
private int N;
private int numOpen;
public Percolation(int n) {
// create n-by-n grid, with all sites blocked
if(n <= 0) {
throw new java.lang.IllegalArgumentException();
}
map = new boolean[n * n + 2];
union = new WeightedQuickUnionUF(n * n +2);
backwash = new WeightedQuickUnionUF(n * n +1);
N = n;
numOpen = 0;
}
public void open(int row, int col) {
// open site (row, col) if it is not open already
if(row <= 0 || row > N || col <= 0 || col > N) {
throw new java.lang.IllegalArgumentException();
}
int index = (row -1) * N + col + 1;
if(map[index]) return;
numOpen++;
map[index] = true;
if(row == 1) {
union.union(index, 0);
backwash.union(index-1, 0);
}
if(row == N) {
union.union(index, 1);
}
if(row != 1 && map[index - N]) {
union.union(index, index-N);
backwash.union(index-1, index-N-1);
}
if(row != N && map[index + N]) {
union.union(index, index+N);
backwash.union(index-1, index+N-1);
}
if(col != 1 && map[index - 1]) {
union.union(index, index-1);
backwash.union(index-1, index-2);
}
if(col != N && map[index + 1]) {
union.union(index, index+1);
backwash.union(index-1, index);
}
}
public boolean isOpen(int row, int col) {
// is site (row, col) open?
if(row <= 0 || row > N || col <= 0 || col > N) {
throw new java.lang.IllegalArgumentException();
}
return map[(row -1) * N + col + 1];
}
public boolean isFull(int row, int col) {
// is site (row, col) full?
if(row <= 0 || row > N || col <= 0 || col > N) {
throw new java.lang.IllegalArgumentException();
}
return backwash.connected((row -1) * N + col, 0);
}
public int numberOfOpenSites() {
// number of open sites
return numOpen;
}
public boolean percolates() {
// does the system percolate?
return union.connected(0,1);
}
public static void main(String[] args) {
// TODO Auto-generated method stub
}
}
这样跑下来是能够获得100分的，但是bonus没有做到。为此还得继续改进。参考了forum中的回答之后，做出如下改动：
（1）只用一个WeightedQuickUnionUF
（2）将map类型改为byte。0表示堵塞，1表示open，2表示full
（3）需多多利用find()函数
（4）只加一个virtualTop
如果开放最后一行的格子，则赋值2，其余赋1.
如果任何一方的root是full的，则将双方Union后的root设为full。
更改后代码如下。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
97import edu.princeton.cs.algs4.In;
import edu.princeton.cs.algs4.StdDraw;
import edu.princeton.cs.algs4.WeightedQuickUnionUF;
public class Percolation {
private byte[] map;
private WeightedQuickUnionUF union;
private int N;
private int numOpen;
public Percolation(int n) {
// create n-by-n grid, with all sites blocked
if(n <= 0) {
throw new java.lang.IllegalArgumentException();
}
map = new byte[n * n + 1];
union = new WeightedQuickUnionUF(n * n +1);
N = n;
numOpen = 0;
map[0] = 1;
}
public void open(int row, int col) {
// open site (row, col) if it is not open already
if(row <= 0 || row > N || col <= 0 || col > N) {
throw new java.lang.IllegalArgumentException();
}
int index = (row -1) * N + col;
if(map[index] != 0) return;
numOpen++;
map[index] = 1;
if(row == 1) {
union.union(0, index);
}
if(row == N) {
map[index] = 2;
map[union.find(index)] = 2;
}
if(row != 1 && map[index - N] != 0) {
int rootUp = union.find(index - N);
int rootCur = union.find(index);
union.union(rootUp, rootCur);
if(map[rootUp] == 2 || map[rootCur] == 2) {
map[union.find(index)] = 2;
}
}
if(row != N && map[index + N] != 0) {
int rootUp = union.find(index + N);
int rootCur = union.find(index);
union.union(rootUp, rootCur);
if(map[rootUp] == 2 || map[rootCur] == 2) {
map[union.find(index)] = 2;
}
}
if(col != 1 && map[index - 1] != 0) {
int rootUp = union.find(index - 1);
int rootCur = union.find(index);
union.union(rootUp, rootCur);
if(map[rootUp] == 2 || map[rootCur] == 2) {
map[union.find(index)] = 2;
}
}
if(col != N && map[index + 1] != 0) {
int rootUp = union.find(index + 1);
int rootCur = union.find(index);
union.union(rootUp, rootCur);
if(map[rootUp] == 2 || map[rootCur] == 2) {
map[union.find(index)] = 2;
}
}
}
public boolean isOpen(int row, int col) {
// is site (row, col) open?
if(row <= 0 || row > N || col <= 0 || col > N) {
throw new java.lang.IllegalArgumentException();
}
return map[(row -1) * N + col] != 0;
}
public boolean isFull(int row, int col) {
// is site (row, col) full?
if(row <= 0 || row > N || col <= 0 || col > N) {
throw new java.lang.IllegalArgumentException();
}
return union.connected((row -1) * N + col, 0);
}
public int numberOfOpenSites() {
// number of open sites
return numOpen;
}
public boolean percolates() {
// does the system percolate?
return map[union.find(0)] == 2;
}
public static void main(String[] args) {
// TODO Auto-generated method stub
}
}