问题描述可以详见：http://coursera.cs.princeton.edu/algs4/assignments/percolation.html
关于QuickFindUF的javadoc:http://algs4.cs.princeton.edu/15uf/QuickFindUF.java.html
关于WeightedQuickUnionUF的javadoc:http://algs4.cs.princeton.edu/15uf/WeightedQuickUnionUF.java.html
附言：（引用于http://blog.csdn.net/revilwang/article/details/10823467）
关于这个模型，其实存在一个问题，在算法课程的论坛上，讨论的热度很高。问题是这样的：
由于引入虚拟的顶层区域和虚拟的底层区域，那么当模型渗透的时候，可能会出现下图的情况
如右边图所示，由于所有的底层区域都和虚拟底层区域相连，所以一旦当区域渗透，则和其他的底层开启区域相连的区域也显示为区域满状态。而实际的情况应该是按照左图所示。这个问题称为 backwash，个人把这个翻译成“回流”。引入虚拟底层区域，很难避免这个问题。讨论的结果，有两种方式可以改进：
1. 不使用虚拟底层区域，只保留顶层，判断是否渗透的时候用虚拟顶层和一个for循环来判断。
2. 保留虚拟底层区域，另外加一个不使用虚拟底层的模型，将两个模型结合在一起来判断是否渗透，通过浪费一些内存来保证效率。
backwash的情况导致Percolation.java在测试时public void isfull(int i, int j) 方法出现错误，这一点从上面两张图也可以明显的看出来。（而解决的办法通过上面两种方法实现)
下面两段代码是从http://www.cnblogs.com/tiny656/p/3820653.html 复制来的，因为自己写的没有考虑到backwash的情况，所以有一些错误，就不挂上来误人子弟了。
Percolation.java
public class Percolation {
private boolean[] matrix;
private int row, col;
private WeightedQuickUnionUF wquUF;
private WeightedQuickUnionUF wquUFTop;
private boolean alreadyPercolates;
public Percolation(int N) {
if (N < 1) throw new IllegalArgumentException("Illeagal Argument");
wquUF = new WeightedQuickUnionUF(N*N+2);
wquUFTop = new WeightedQuickUnionUF(N*N+1);
alreadyPercolates = false;
row = N;
col = N;
matrix = new boolean[N*N+1];
}
private void validate(int i, int j) {
if (i < 1 || i > row)
throw new IndexOutOfBoundsException("row index i out of bounds");
if (j < 1 || j > col)
throw new IndexOutOfBoundsException("col index j out of bounds");
}
public void open(int i, int j) {
validate(i, j);
int curIdx = (i-1)*col + j;
matrix[curIdx] = true;
if (i == 1) {
wquUF.union(curIdx, 0);
wquUFTop.union(curIdx, 0);
}
if (i == row) {
wquUF.union(curIdx, row*col+1);
}
int[] dx = {1, -1, 0, 0};
int[] dy = {0, 0, 1, -1};
for (int dir = 0; dir < 4; dir++) {
int posX = i + dx[dir];
int posY = j + dy[dir];
if (posX <= row && posX >= 1
&& posY <= row && posY >= 1
&& isOpen(posX, posY)) {
wquUF.union(curIdx, (posX-1)*col+posY);
wquUFTop.union(curIdx, (posX-1)*col+posY);
}
}
}
public boolean isOpen(int i, int j) {
validate(i, j);
return matrix[(i-1)*col + j];
}
public boolean isFull(int i, int j) {
validate(i, j);
int curIdx = (i-1)*col+j;
if (wquUFTop.find(curIdx) == wquUFTop.find(0)) return true;
return false;
}
public boolean percolates() {
if (alreadyPercolates) return true;
if (wquUF.find(0) == wquUF.find(row*col+1)) {
alreadyPercolates = true;
return true;
}
return false;
}
public static void main(String[] args) {
Percolation perc = new Percolation(2);
perc.open(1, 1);
perc.open(1, 2);
perc.open(2, 1);
System.out.println(perc.percolates());
}
}
PercolationStats.java
public class PercolationStats {
private double[] x;
private int expTime;
public PercolationStats(int N, int T) { // perform T independent experiments on an N-by-N grid
if (N <= 0 || T <= 0)
throw new IllegalArgumentException("Illeagal Argument");
x = new double[T+1];
expTime = T;
for (int i = 1; i <= T; i++) {
Percolation perc = new Percolation(N);
while (true) {
int posX, posY;
do {
posX = StdRandom.uniform(N) + 1;
posY = StdRandom.uniform(N) + 1;
} while(perc.isOpen(posX, posY));
perc.open(posX, posY);
x[i] += 1;
if (perc.percolates())
break;
}
x[i] = x[i]/(double) (N * N);
}
}
public double mean() { // sample mean of percolation threshold
double u = 0.0;
for (int i = 1; i <= expTime; i++) {
u += x[i];
}
return u / (double)expTime;
}
public double stddev() { // sample standard deviation of percolation threshold
double q = 0.0;
double u = mean();
for (int i = 1; i <= expTime; i++) {
q += (x[i]-u)*(x[i]-u);
}
return Math.sqrt(q / (double)(expTime - 1));
}
public double confidenceLo() { // low endpoint of 95% confidence interval
double mu = mean();
double sigma = stddev();
return mu - 1.96*sigma / Math.sqrt(expTime);
}
public double confidenceHi() { // high endpoint of 95% confidence interval
double mu = mean();
double sigma = stddev();
return mu + 1.96*sigma / Math.sqrt(expTime);
}
public static void main(String[] args) { // test client (described below)
int N = Integer.parseInt(args[0]);
int T = Integer.parseInt(args[1]);
PercolationStats percStats = new PercolationStats(N, T);
StdOut.printf("mean = %f\n", percStats.mean());
StdOut.printf("stddev = %f\n", percStats.stddev());
StdOut.printf("95%% confidence interval = %f, %f\n",
percStats.confidenceLo(), percStats.confidenceHi());
}
}