Java中的渗流

Question

我在java中使用加权快速联合的过滤程序时遇到了问题。我认为主要是因为我使用联合来判断连接了哪些位置，或者我正在运行的测试有问题，以查看网格是否过滤。如果有人有反馈，我将不胜感激

/* a class to test for percolation of an N by N grid*/
public class Percolation{
  WeightedQuickUnionUF uf;
  boolean[][] grid;
  public int size;
  int opensites;//keeps track of open sites


 /*Constructor for Percolation that takes N as an argument 
  * to create an N*N grid
  **/
  public Percolation(int N){
    this.size=N;
    int spaces= N*N;
    uf = new WeightedQuickUnionUF(spaces+1);//initializes the WQUUF data structure.
    opensites=0;//intializes open sites to 0.
    this.grid = new boolean[N][N];// makes a boolean array 2D N by N representing the grid 
    for(int i=0;i<N;i++){//i represents the x coordinate
      for(int j=0;j<N;j++){// j represents the y coordinate
        grid[i][j]=false; //sets all spaces as closed
      }//end j loop
    }//end i loop

    for(int i=0;i<size;i++){
      uf.union(size*size,i);
    }// end for that connects all top sites
  }// end constructor;



/*
 * takes to ints as X and Y coordinates 
 * and opens that square on the grid
 **/
  public void open(int i, int j){

    if(!(this.grid[i][j])){
      this.grid[i][j]=true;
      opensites+=1;
    }
  }//end open


/*
 * takes to ints as X and Y coordinates and 
 * returns true if that space is open and false
 * if not
 **/
  public boolean isOpen(int i, int j){
    return grid[i][j];
  }//end isOpen




  /* 
   * takes to ints as X and Y coordinates and 
   * returns true if that space is full and false
   * if not
   */
  public boolean isFull(int i, int j){
    if(isOpen(i,j)){
      if(uf.connected((i+j*size),(size*size))){ return true;}
    }//end for
    return false;
  }//end isFull

  /* 
   * checks if any space on the bottom is full returns true 
   * if there is one false other wise
   */
  public boolean percolates(){
    for(int i=0;i<size;i++){
      if(isFull(i,size-1)) return true;
    }
    return false;
  }//end percolates

  /*
   * prints out grid 
   * ---------------------
   * 0 false true false
   * 1 true true true
   * 2 false true true
   * ---------------------
   */
  public void printGrid(){
    StdOut.println("----------------------------------");
    for(int x = 0;x < size;x++){
      for(int y = 0; y < size; y++){
        String mark=isOpen(x,y) ? "x": "0";
        StdOut.print("|"+mark+"|");

      }
      StdOut.println();
    }
    StdOut.println("----------------------------------");
  }


/*
 * Main method takes two int arguments one for the number 
 * of tests to be run and one for the size of the grid
 **/
  public static void main(String[] args) {
    int tests=StdIn.readInt();
    int size=StdIn.readInt();
    int testedTimes=1;
    int spaces=size*size-1;
    int check=0;
    int space=0;
    while(testedTimes<=tests){
      Percolation perc = new Percolation(size);
      StdOut.println("Before anything");
      perc.printGrid();
      while(!perc.percolates()){
        int x=StdRandom.uniform(0,size);
        int y=StdRandom.uniform(0,size);

        perc.open(x,y);
        space=x+(y*size);
        if((space+1<spaces)&&(x<size-1)){//right 1
          if(perc.isOpen(x+1,y)){
            perc.uf.union(space,space+1);
          }
        }
        if((space-1>0)&&(x>0)){//left 1
          if(perc.isOpen(x-1,y)){
            perc.uf.union(space,space-1);
          }
        }
        if((space-size>0)&&(y-1>0)){//up 1
          if(perc.isOpen(x,y-1)){
            perc.uf.union(space,space-size);
          }
        }
        if((space+size<spaces)&&(y+1<=size)){//down 1
          if((perc.isOpen(x,y+1))){
            perc.uf.union(space,space+size);
          }
          perc.printGrid();
        }

      }//end while(!percolates())
      testedTimes++;
    }//end while(TestedTimes<tests)
  }//end main.
}//end class

Answer 1

import edu.princeton.cs.algs4.WeightedQuickUnionUF;

public class Percolation {
private boolean[][] grid;
private int len;
private int top = 0;
private int bottom;
private WeightedQuickUnionUF uf;
private int count = 0;

// creates n-by-n grid, with all sites initially blocked
public Percolation(int n) {
    if (n <= 0) {
        throw new IllegalArgumentException();
    }
    len = n;
    grid = new boolean[n][n];
    bottom = n * n + 1;
    uf = new WeightedQuickUnionUF(n * n + 2);
}

// opens the site (row, col) if it is not open already
public void open(int row, int col) {
    if (row < 1 || col < 1 || row > len || col > len) {
        throw new IllegalArgumentException();
    }
    int i = row - 1;
    int j = col - 1;
    if (!isOpen(row, col)) {
        count++;
        grid[i][j] = true;
        if (row == 1) {
            uf.union(getIndex(row, col), top);
        }
        if (row == len) {
            uf.union(getIndex(row, col), bottom);
        }

        // union the neighbors
        // down
        if (row < len && isOpen(row + 1, col)) {
            uf.union(getIndex(row, col), getIndex(row + 1, col));
        }
        // up
        if (row > 1 && isOpen(row - 1, col)) {
            uf.union(getIndex(row, col), getIndex(row - 1, col));
        }
        // left
        if (col > 1 && isOpen(row, col - 1)) {
            uf.union(getIndex(row, col), getIndex(row, col - 1));
        }
        // right
        if (col < len && isOpen(row, col + 1)) {
            uf.union(getIndex(row, col), getIndex(row, col + 1));
        }
    }
}

// is the site (row, col) open?
public boolean isOpen(int row, int col) {
    if (row < 1 || col < 1 || row > len || col > len) {
        throw new IllegalArgumentException();
    }
    return grid[row - 1][col - 1];
}

// is the site (row, col) full?
public boolean isFull(int row, int col) {
    if (row < 1 || col < 1 || row > len || col > len) {
        throw new IllegalArgumentException();
    }
    return (uf.find(getIndex(row, col)) == uf.find(top));
}

// returns the number of open sites
public int numberOfOpenSites() {
    return count;
}

// does the system percolate?
public boolean percolates() {
    return (uf.find(top) == uf.find(bottom));
}

// get the index if row,column
private int getIndex(int row, int col) {
    return len * (row - 1) + (col);
}

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

}
}

Answer 2

稍晚一点回复，我将编写下面的渗透代码

我用这些注释来说明每一行和变量应该做什么

public class Percolation {

// Length of the square grid "gridLength * gridLength"
private int gridLength;

// Array representing indexes of all sites (either it"s open or blocked)
private boolean[] sites;

// Number of open sites
private int openSitesNumber;

// Index of the top virtual site (has value 0)
private int virtualTopIndex;

// Index of the top virtual site (has value (gridLength * gridLength) + 1)
private int virtualBottomIndex;

// Weighted quick union-find data structure
// to calculate percolation
private WeightedQuickUnionUF ufForPercolation;

// Weighted quick union-find data structure
// to calculate fullness (without bottom virtual site)
private WeightedQuickUnionUF ufForFullness;

// Create n-by-n grid, with all sites blocked
public Percolation(int n) {
    if (n < 1) {
        throw new IllegalArgumentException("Grid must have at least one row and column");
    }

    gridLength = n;
    int gridSize = (n * n) + 2; // with two virtual sites
    sites = new boolean[gridSize];
    openSitesNumber = 0;

    // init and open virtual sites
    virtualTopIndex = 0;
    virtualBottomIndex = (gridLength * gridLength) + 1;
    sites[virtualTopIndex] = true;
    sites[virtualBottomIndex] = false;

    ufForPercolation = new WeightedQuickUnionUF(gridSize);
    ufForFullness = new WeightedQuickUnionUF(gridSize);

    // connect top and bottom rows to virtual sites
    for (int col = 1; col <= gridLength; col++) {
        int rowTop = 1;
        int siteTopIndex = getIndexByRowAndColumn(rowTop, col);
        ufForPercolation.union(virtualTopIndex, siteTopIndex);
        ufForFullness.union(virtualTopIndex, siteTopIndex);

        int rowBottom = gridLength;
        int siteBottomIndex = getIndexByRowAndColumn(rowBottom, col);
        ufForPercolation.union(virtualBottomIndex, siteBottomIndex);
    }
}

// Open site (row, col) if it is not open already
public void open(int row, int col)
{
    int siteIndex = getIndexByRowAndColumn(row, col);
    if (sites[siteIndex]) {
        return;
    }

    openSitesNumber++;
    sites[siteIndex] = true;

    // connect with left neighbor
    if (col > 1 && isOpen(row, col - 1)) {
        int siteLeftIndex = getIndexByRowAndColumn(row, col - 1);
        ufForPercolation.union(siteIndex, siteLeftIndex);
        ufForFullness.union(siteIndex, siteLeftIndex);
    }

    // connect with right neighbor
    if (col < gridLength && isOpen(row, col + 1)) {
        int siteLeftIndex = getIndexByRowAndColumn(row, col + 1);
        ufForPercolation.union(siteIndex, siteLeftIndex);
        ufForFullness.union(siteIndex, siteLeftIndex);
    }

    // connect with top neighbor
    if (row > 1 && isOpen(row - 1, col)) {
        int siteLeftIndex = getIndexByRowAndColumn(row - 1, col);
        ufForPercolation.union(siteIndex, siteLeftIndex);
        ufForFullness.union(siteIndex, siteLeftIndex);
    }

    // connect with bottom neighbor
    if (row < gridLength && isOpen(row + 1, col)) {
        int siteLeftIndex = getIndexByRowAndColumn(row + 1, col);
        ufForPercolation.union(siteIndex, siteLeftIndex);
        ufForFullness.union(siteIndex, siteLeftIndex);
    }
}

// If site (row, col) open
public boolean isOpen(int row, int col)
{
    int siteIndex = getIndexByRowAndColumn(row, col);

    return sites[siteIndex];
}

// If site (row, col) full
public boolean isFull(int row, int col)
{
    int siteIndex = getIndexByRowAndColumn(row, col);

    return (isOpen(row, col) && ufForFullness.connected(virtualTopIndex, siteIndex));
}

// Number of open sites
public int numberOfOpenSites()
{
    return openSitesNumber;
}

// If the system percolate
public boolean percolates()
{
    // if grid with one site - check if it"s open
    if (gridLength == 1) {
        int siteIndex = getIndexByRowAndColumn(1, 1);
        return sites[siteIndex];
    }

    return ufForPercolation.connected(virtualTopIndex, virtualBottomIndex);
}

// Get site"s index to be represented in array
private int getIndexByRowAndColumn(int row, int col)
{
    validateBounds(row, col);

    return ((row - 1) * gridLength) + col;
}

// Check if row and column values are in range of grid size
private void validateBounds(int row, int col)
{
    if (row > gridLength || row < 1) {
        throw new IndexOutOfBoundsException("Row index is out of bounds");
    }

    if (col > gridLength || col < 1) {
        throw new IndexOutOfBoundsException("Column index is out of bounds");
    }
}

// Test client (optional)
public static void main(String[] args)
{
    Percolation percolation = new Percolation(2);

    StdOut.println("percolates = " + percolation.percolates());

    StdOut.println("isOpen(1, 2) = " + percolation.isOpen(1, 2));
    StdOut.println("isFull(1, 2) = " + percolation.isFull(1, 2));
    StdOut.println("open(1, 2)");
    percolation.open(1, 2);
    StdOut.println("isOpen(1, 2) = " + percolation.isOpen(1, 2));
    StdOut.println("isFull(1, 2) = " + percolation.isFull(1, 2));
    StdOut.println("numberOfOpenSites() = " + percolation.numberOfOpenSites());
    StdOut.println("percolates() = " + percolation.percolates());

    StdOut.println("isOpen(2, 1) = " + percolation.isOpen(2, 1));
    StdOut.println("isFull(2, 1) = " + percolation.isFull(2, 1));
    StdOut.println("open(2, 1)");
    percolation.open(2, 1);
    StdOut.println("isOpen(2, 1) = " + percolation.isOpen(2, 1));
    StdOut.println("isFull(2, 1) = " + percolation.isFull(2, 1));
    StdOut.println("numberOfOpenSites() = " + percolation.numberOfOpenSites());
    StdOut.println("percolates() = " + percolation.percolates());

    StdOut.println("isOpen(1, 1) = " + percolation.isOpen(1, 1));
    StdOut.println("isFull(1, 1) = " + percolation.isFull(1, 1));
    StdOut.println("open(1, 1)");
    percolation.open(1, 1);
    StdOut.println("isOpen(1, 1) = " + percolation.isOpen(1, 1));
    StdOut.println("isFull(1, 1) = " + percolation.isFull(1, 1));
    StdOut.println("numberOfOpenSites() = " + percolation.numberOfOpenSites());
    StdOut.println("percolates() = " + percolation.percolates());
}

}

Answer 3

在我看来，你是从左到右渗透，而不是从上到下渗透（你使用i作为列，j作为行）

尝试更改打印网格，使用等参线（y，x）而不是等参线（x，y）