Ask Question

Name:
Title:
Your Question:

Answer Question

Name:
Your Answer:
User Submitted Source Code!


Description:
  Percolation
Language: JAVA
Code:
public class Percolation 
{
     public Percolation(int N) 
     {
          this.N = N;
          size = N * N;
          id = new int[size];
          sz = new int[size];
          open = new boolean[size];
          full = new boolean[size];
          for (int i = 0; i < N; i++)
          {
               id[i] = i;
               sz[i] = 1;
               open[i] = false;
               full[i] = false;
          }
     }
     
     public void open(int i, int j)
     {
          if (i < 1 || i > N) throw IndexOutOfBoundsException;
          if (j < 1 || j > N) throw IndexOutOfBoundsException;
          if (isOpen(i, j))
               return;
          int p = index(i, j);
          int q;
          open[p] = true;
          if (p < N) full[p] = true;
          if (i > 1) 
          {
               q = index(i - 1, j);
               union(p, q);
               if (full[p] && open[q]) full[q] = true;
               else if (full[q] && open[q]) full[p] = true;
          }
          if (i < N) 
          {
               q = index(i + 1, j);
               union(p, q);
               if (full[p] && open[q]) full[q] = true;
               else if (full[q] && open[q]) full[p] = true;
          }
          if (j > 1) 
          {
               q = index(i, j - 1);
               union(p, q);
               if (full[p] && open[q]) full[q] = true;
               else if (full[q] && open[q]) full[p] = true;
          }
          
          if (j < N) 
          {
               q = index(i, j + 1);
               union(p, q);
               if (full[p] && open[q]) full[q] = true;
               else if (full[q] && open[q]) full[p] = true;
          }
     }
     
     public boolean isOpen(int i, int j)
     {
          return open[index(i, j)];
     }
     
     public boolean isFull(int i, int j)
     {
          return full[index(i, j)];
     }
     
     public boolean percolates() 
     {
          for (int c = 1; c <= N; c++)
          {
               if (connected(index(1, c), index(N, c)))
                    return true;
          }
          return false;
     }
     
     private int index(int r, int c)
     {
          return N * (r - 1) + (c - 1);
     }
     
     private int root(int i)
     {
          while (i != id[i]) 
          {
               id[i] = id[id[i]];
               i = id[i];
          }
          return i;
     }
     
     private void union(int p, int q)
     {
          int i = root(p);
          int j = root(q);
          if (sz[i] < sz[j]) { id[i] = j; sz[j] += sz[i]; }
          else                   { id[j] = i; sz[i] += sz[j]; }
     }
     
     private boolean connected(int p, int q)
     {
          return root(p) == root(q);
     }
     
     private int[] id;
     private int[] sz;
     private boolean[] open;
     private boolean[] full;
     private int N;
     private int size;
}
Comments: