JAVA--Fill in the TODO\'s package algs15.perc; //import stdlib.*; // Uncomment t

Question

JAVA--Fill in the TODO's

package algs15.perc;

//import stdlib.*;

// Uncomment the import statements above.

// You can test this using InteractivePercolationVisualizer and PercolationVisualizer
// All methods should make at most a constant number of calls to the UF data structure,
// except percolates(), which may make up to N calls to the UF data structure.
public class Percolation {
   int N;
   boolean[] open;
   // TODO: more fields to add here
   public Percolation(int N) {
       this.N = N;
       this.open = new boolean[N*N];
       // TODO: more to do here
   }
   // open site (row i, column j) if it is not already
   public void open(int i, int j) {
       open[i*N+j] = true;
       // TODO: more to do here.
   }
   // is site (row i, column j) open?
   public boolean isOpen(int i, int j) {
       return open[i*N+j];
   }
   // is site (row i, column j) full?
   public boolean isFull(int i, int j) {
       // TODO
       return false;
   }
   // does the system percolate?
   public boolean percolates() {
       // TODO
       return false;
   }
}

Explanation / Answer

public class Percolation {

private boolean[][] opened;
private int top = 0;
private int bottom;
private int size;
private WeightedQuickUnionUF qf;

public Percolation(int N) {
size = N;
bottom = size * size + 1;
qf = new WeightedQuickUnionUF(size * size + 2);
opened = new boolean[size][size];
}

  
//Open site (row i, column j) if it is not already.

public void open(int i, int j) {
opened[i - 1][j - 1] = true;
if (i == 1) {
qf.union(getQFIndex(i, j), top);
}
if (i == size) {
qf.union(getQFIndex(i, j), bottom);
}

if (j > 1 && isOpen(i, j - 1)) {
qf.union(getQFIndex(i, j), getQFIndex(i, j - 1));
}
if (j < size && isOpen(i, j + 1)) {
qf.union(getQFIndex(i, j), getQFIndex(i, j + 1));
}
if (i > 1 && isOpen(i - 1, j)) {
qf.union(getQFIndex(i, j), getQFIndex(i - 1, j));
}
if (i < size && isOpen(i + 1, j)) {
qf.union(getQFIndex(i, j), getQFIndex(i + 1, j));
}
}

  
//Is site (row i, column j) open?

public boolean isOpen(int i, int j) {
return opened[i - 1][j - 1];
}

  
//Is site (row i, column j) full?

public boolean isFull(int i, int j) {
if (0 < i && i <= size && 0 < j && j <= size) {
return qf.connected(top, getQFIndex(i , j));
} else {
throw new IndexOutOfBoundsException();
}
}

//Does the system percolate?
public boolean percolates() {
return qf.connected(top, bottom);
}

private int getQFIndex(int i, int j) {
return size * (i - 1) + j;
}
}

Related Questions

Navigate

• Browse (All)
• Browse J
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.