渗透模型

11月7日 · 2017年
jxtxzzw · ·

这是一道并查集的问题。

public class Percolation {

    private final int[][] DIRECTIONS = { { -1, 0 }, { 1, 0 }, { 0, -1 }, { 0, 1 } };
    private final int X_OFFSET = 0;
    private final int Y_OFFSET = 1;

    private boolean[][] openStatus;
    private boolean[][] fullStatus;
    private int n;
    private WeightedQuickUnionUF disjointSet;

    public Percolation(int n) throws java.lang.IllegalArgumentException {
        if (n <= 0)
            halt();
        this.n = n;
        openStatus = new boolean[n + 1][n + 1];
        fullStatus = new boolean[n + 1][n + 1];
        for (int row = 1; row <= n; row++) {
            for (int col = 1; col <= n; col++) {
                openStatus[row][col] = false;
                fullStatus[row][col] = false;
            }
        }
        disjointSet = new WeightedQuickUnionUF(n * n + 1);
    }

    private void halt() throws IllegalArgumentException {
        throw new java.lang.IllegalArgumentException();
    }

    public void open(int row, int col) throws java.lang.IllegalArgumentException {
        if (isValid(row, col)) {
            openStatus[row][col] = true;
            for (int direction = 0; direction < 4; ++direction) {
                int newRow = row + DIRECTIONS[direction][X_OFFSET];
                int newCol = col + DIRECTIONS[direction][Y_OFFSET];
                if (isValid(newRow, newCol)) {
                    if (isOpen(newRow, newCol)) {
                        int unionIndexP = (row - 1) * n + col;
                        int unionIndexQ = (newRow - 1) * n + newCol;
                        disjointSet.union(unionIndexP, unionIndexQ);
                    }
                }
            }
            fullStatus[row][col] = connectedWithTop(row, col);
        } else {
            halt();
        }
    }

    private boolean connectedWithTop(int row, int col) {
        int unionIndex = (row - 1) * n + col;
        for (int topIndex = 1; topIndex <= n; ++topIndex) {
            if (disjointSet.connected(topIndex, unionIndex))
                return true;
        }
        return false;
    }

    private boolean isValid(int row, int col) {
        return (row>=1 && row<=n && col>=1 && col<=n);      
    }

    public boolean isOpen(int row, int col) throws java.lang.IllegalArgumentException {
        if (!isValid(row,col))
            halt();
        return  openStatus[row][col];
    }

    public boolean isFull(int row, int col) throws java.lang.IllegalArgumentException {
        if (!isValid(row,col))
            halt();
        return fullStatus[row][col];
    }

    public int numberOfOpenSites() {
        int counter = 0;
        for (int row = 1; row <= n; ++row) {
            for (int col = 1; col <= n; ++col) {
                if (isOpen(row, col))
                    counter++;
            }
        }
        return counter;
    }

    public boolean percolates() {
        flush();
        final int BOTTOM = n;
        for (int bottomIndex = 1; bottomIndex <= n; ++bottomIndex) {
            if (isOpen(BOTTOM, bottomIndex) && isFull(BOTTOM, bottomIndex))
                return true;
        }
        return false;
    }

    private void flush() {
        for (int row = 1; row <= n; row++) {
            for (int col = 1; col <= n; col++) {
                fullStatus[row][col] = connectedWithTop(row, col);
            }
        }
    }

}
public class PercolationGUI extends JPanel {

    private static final long serialVersionUID = -5258995676212660595L;
    private static final int GRID_SIZE = 10;

    private final int[][] DIRECTIONS = { { -1, 0 }, { 1, 0 }, { 0, -1 }, { 0, 1 } };
    private final int X_OFFSET = 0;
    private final int Y_OFFSET = 1;

    private boolean[][] openStatus;
    private boolean[][] fullStatus;
    private int n;
    private WeightedQuickUnionUF disjointSet;

    public PercolationGUI(int n) throws java.lang.IllegalArgumentException {
        if (n <= 0)
            halt();
        this.n = n;
        openStatus = new boolean[n + 1][n + 1];
        fullStatus = new boolean[n + 1][n + 1];
        for (int row = 1; row <= n; row++) {
            for (int col = 1; col <= n; col++) {
                openStatus[row][col] = false;
                fullStatus[row][col] = false;
            }
        }
        disjointSet = new WeightedQuickUnionUF(n * n + 1);
    }

    private void halt() throws IllegalArgumentException {
        throw new java.lang.IllegalArgumentException();
    }

    public void open(int row, int col) throws java.lang.IllegalArgumentException {
        if (isValid(row, col)) {
            openStatus[row][col] = true;
            for (int direction = 0; direction < 4; ++direction) {
                int newRow = row + DIRECTIONS[direction][X_OFFSET];
                int newCol = col + DIRECTIONS[direction][Y_OFFSET];
                if (isValid(newRow, newCol)) {
                    if (isOpen(newRow, newCol)) {
                        int unionIndexP = (row - 1) * n + col;
                        int unionIndexQ = (newRow - 1) * n + newCol;
                        disjointSet.union(unionIndexP, unionIndexQ);
                    }
                }
            }
            fullStatus[row][col] = connectedWithTop(row, col);
        } else {
            halt();
        }
    }

    private void flush() {
        for (int row = 1; row <= n; row++) {
            for (int col = 1; col <= n; col++) {
                fullStatus[row][col] = connectedWithTop(row, col);
            }
        }
    }

    private boolean connectedWithTop(int row, int col) {
        int unionIndex = (row - 1) * n + col;
        for (int topIndex = 1; topIndex <= n; ++topIndex) {
            if (disjointSet.connected(topIndex, unionIndex))
                return true;
        }
        return false;
    }

    private boolean isValid(int row, int col) {
        return (row>=1 && row<=n && col>=1 && col<=n);      
    }

    public boolean isOpen(int row, int col) throws java.lang.IllegalArgumentException {
        if (!isValid(row,col))
            halt();
        return  openStatus[row][col];
    }

    public boolean isFull(int row, int col) throws java.lang.IllegalArgumentException {
        if (!isValid(row,col))
            halt();
        return fullStatus[row][col];
    }

    public int numberOfOpenSites() {
        int counter = 0;
        for (int row = 1; row <= n; ++row) {
            for (int col = 1; col <= n; ++col) {
                if (isOpen(row, col))
                    counter++;
            }
        }
        return counter;
    }

    public boolean percolates() {
        flush();
        final int BOTTOM = n;
        for (int bottomIndex = 1; bottomIndex <= n; ++bottomIndex) {
            if (isOpen(BOTTOM, bottomIndex) && isFull(BOTTOM, bottomIndex))
                return true;
        }
        return false;
    }

    @Override
    public void paint(Graphics graphics) {
        super.paint(graphics);
        for (int row = 1; row <= n; row++) {
            for (int col = 1; col <= n; col++) {
                Color setColor = Color.WHITE;
                if (isOpen(row, col)) {
                    if (isFull(row, col)) {
                        setColor = new Color(103, 198, 243);
                    } else {
                        setColor = Color.WHITE;
                    }
                } else {
                    setColor = Color.BLACK;
                }
                draw(graphics, col * GRID_SIZE, row * GRID_SIZE, GRID_SIZE, setColor);
            }
        }
    }

    @Override
    public Dimension getPreferredSize() {
        return new Dimension((n + 2) * GRID_SIZE + 1, (n + 2) * GRID_SIZE + 1);
    }

    public void draw(Graphics graphics, int xPix, int yPix, int size, Color setColor) {
        graphics.setColor(Color.BLACK);
        graphics.drawRect(xPix, yPix, size, size);
        graphics.setColor(setColor);
        graphics.fillRect(xPix, yPix, size, size);
    }

    public void showGUI() {
        flush();
        JFrame frame = new JFrame();
        frame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
        frame.setResizable(false);
        frame.setTitle("PercolationGUI");
        frame.add(this);
        frame.pack();
        frame.setVisible(true);
        try {
            Thread.sleep(1000);
        } catch (InterruptedException e) {
            e.printStackTrace();
        }
        frame.dispose();
    }

}

public class PercolationStats { private double thresholds[]; public PercolationStats(int n, int trials) { if (!isValid(n, trials)) throw new java.lang.IllegalArgumentException(); thresholds = new double[trials]; for (int i = 0; i < trials; ++i) { // Percolation p = new Percolation(n); PercolationGUI p = new PercolationGUI(n); while (!p.percolates()) { int possibleRow = StdRandom.uniform(1, n + 1); int possibleCol = StdRandom.uniform(1, n + 1); p.open(possibleRow, possibleCol); } thresholds[i] = (double) (p.numberOfOpenSites()) / (double) (n * n); p.showGUI(); } } private boolean isValid(int n, int trials) { return n > 0 && trials > 0; } public double mean() { return StdStats.mean(thresholds); } public double stddev() { return StdStats.stddev(thresholds); } public double confidenceLo() { return mean() - 1.96 * stddev() / Math.sqrt(thresholds.length); } public double confidenceHi() { return mean() + 1.96 * stddev() / Math.sqrt(thresholds.length); } public static void main(String[] args) { PercolationStats ps = new PercolationStats(50, 500); System.out.println("mean=" + ps.mean()); System.out.println("stddev=" + ps.stddev()); System.out.println("95% confidence interval=[" + ps.confidenceLo() + "," + ps.confidenceHi() + "]"); System.out.println((ps.confidenceLo() + ps.confidenceHi()) / 2); } }
0 条回应
验证码
输入运算符及数字使等式成立
{{comment.validate_num1}} = {{comment.validate_num2}}
点赞确定
退出登录?
取消 确定