《Algorithms》作业1：Percolation

题意

原题目：http://coursera.cs.princeton.edu/algs4/assignments/percolation.html

percolate 渗透，扩散
给定一个正方形的图，图上每个点(site)的状态初始为非open，即下图中的黑色部分，现在随机逐个打开其中的某些site，使之转变为open状态，判断上下是否联通，即相当于从图上方灌水，问是否能渗透到最底下。

现在把能够渗透的状态称为percolate
若要表示图percolate的概率和单个点open的概率的关系，可以用以下的曲线图表示：

左边的是20x20的图，右边是100x100的矩阵。

要完成的任务Percolation.java如下：

public class Percolation {
   public Percolation(int n)                // create n-by-n grid, with all sites blocked
   public void open(int row, int col)       // open site (row, col) if it is not open already
   public boolean isOpen(int row, int col)  // is site (row, col) open?
   public boolean isFull(int row, int col)  // is site (row, col) full?
   public boolean percolates()              // does the system percolate?

   public static void main(String[] args)   // test client (optional)
}

具体要求参见原题。

解决方案

如何将二维图投射到一维

so easy！

private int Index(int i, int j) {
        return i * N + j;
}

什么是isFull状态

即从上到下渗透的过程中，被“填充”的open位置的状态。

如何open

对于public void open(int row, int col)方法，有如下的解决方案：

1. 将Index(row, col)位置的site打开
2. 判断上下左右是否打开，若打开，union之。

但是这个方案有个很大的缺点，即所谓的backwash问题：在percolate之前，有些块位于图的最下方，与底部相连通，一旦percolate，这些点也会被认为是isFull状态的，这与事实不符。
故提出如下改进的解决方案：

1. 设置每个点的状态有ConnectToTop和ConnectToBottom，即是否与上和下联通。
2. open时，将Index(i, j)位置的site打开，union操作同之前的方案。
3. 若相邻的Index(i+dx[k]，j+dy[k])的root或者目前位置的root与top联通，则该位置的root为ConnectToTop，bottom同理。
4. 若ConnectToTop并且ConnectToBottom，则percolate。

代码

下面给出Percolation.java的代码

import edu.princeton.cs.algs4.WeightedQuickUnionUF;

public class Percolation {
    private WeightedQuickUnionUF uf;
    private int N;
    private boolean[] openSites;
    private boolean[] ConnectToTop;
    private boolean[] ConnectToBottom;
    private boolean isPercolate;
    private int[] dx = {0,1,0,-1};
    private int[] dy = {1,0,-1,0};
    
    public Percolation(int N){
        this.N = N;
        uf = new WeightedQuickUnionUF((N + 1)*(N + 1));
        openSites = new boolean[(N + 1) * (N + 1)];
        ConnectToTop = new boolean[(N + 1) * (N + 1)];
        ConnectToBottom = new boolean[(N + 1) * (N + 1)];
        isPercolate = false;
        for (int i = 0; i < ((N+1)*(N+1)); i++) {
             openSites[i] = false;
             ConnectToTop[i] = false;
             ConnectToBottom[i] = false;
        }
        for (int i = 1; i <= N; ++i){
            uf.union(1, i);
            openSites[Index(0,1)] = true;
        }
    }
    
    private int Index(int i, int j) {
        return i * N + j;
    }
    
    private void CorrectPosition(int i, int j) {
        if (!(i >= 1 && i <= N && j >= 1 && j <= N)) {
            throw new IndexOutOfBoundsException("BOOM SHAKALAKA");
        }
    }
    
    
    //public void open(int row, int col)       
    // open site (row, col) if it is not open already
    public void open(int i, int j) {
        CorrectPosition(i, j);
        if (openSites[Index(i, j)]) return;
        openSites[Index(i, j)] = true;
        boolean WithTop = false;
        boolean WithBottom = false;
        WithTop = (i == 1);
        WithBottom = (i == N);
        for (int k = 0; k < 4; ++k){
            if (j + dy[k] < 1 || j + dy[k] > N) continue;
            if (openSites[Index(i + dx[k], j + dy[k])]) {
                if ( ConnectToTop[uf.find(Index(i + dx[k], j + dy[k]))]
                        || ConnectToTop[uf.find(Index(i, j))] ) {   
                    WithTop = true;
                }
                if (ConnectToBottom[uf.find(Index(i + dx[k], j + dy[k]))]
                        || ConnectToBottom[uf.find(Index(i, j))] ) {   
                    WithBottom = true;
                }
                uf.union(Index(i, j), Index(i + dx[k], j + dy[k]));
            }
        }
        ConnectToTop[uf.find(Index(i, j))] = WithTop;
        ConnectToBottom[uf.find(Index(i, j))] = WithBottom;
        if (WithTop && WithBottom){
            isPercolate = true;
        }
    }
    
    //public boolean isOpen(int row, int col)  
    // is site (row, col) open?
    public boolean isOpen(int row, int col){
        CorrectPosition(row, col);
        return openSites[Index(row,col)];
    }
    
    public boolean isFull(int row, int col){
        CorrectPosition(row, col);
        return ConnectToTop[uf.find(Index(row ,col))];
    }
    
    public boolean percolates(){
        return isPercolate;
    }
}