Percolation

Percolation.java

主要问题为backwash。其形成原因为：因为存在上下两个虚拟节点，当percolates()为true上下贯通时，所有在最底排的已经打开的节点都会变成与上虚拟节点连通(每打开一个底部节点，都会将其与下虚拟节点连通)。解决方法是再设置一个union-find，但只提供上虚拟节点，将isFull()放在第二个union-find中进行判断。

为了方便处理，将二维数组坐标转化为一维数组坐标进行处理。

import edu.princeton.cs.algs4.WeightedQuickUnionUF;public class Percolation {private int count;          				// number of open sitesprivate boolean[] isOpenSite;private final int n;private final int vTop;           			// the virtual top nodeprivate final int vBottom;       			// the virtual bottom nodeprivate final WeightedQuickUnionUF uf;private final WeightedQuickUnionUF ufBW;    // to avoid backwashpublic Percolation(int n) {if (n <= 0) {throw new IllegalArgumentException();}count = 0;this.n = n;vTop = 0;vBottom = n * n + 1;isOpenSite = new boolean[n * n + 2];uf = new WeightedQuickUnionUF(n * n + 2);ufBW = new WeightedQuickUnionUF(n * n + 2);isOpenSite[vTop] = true;isOpenSite[vBottom] = true;}public boolean isOpen(int row, int col) {check(row, col);return isOpenSite[toIndex(row, col)];}public boolean isFull(int row, int col) {check(row

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！