CODEWITHSUNDEEP
javarecursionmatrixdepth-first-search
user1189352
user1189352

Reputation: 3885

Using Depth First Search to traverse a Matrix to find out Percolation

I'm trying to write a boolean method that will return if a matrix is "full" or not

(A full site is an open site that can be connected to an open site in the top row via a chain of neighboring (left, right, up, down) open sites.)

for the grid, true = open site

I'm still learning recursion and I read somewhere that DFS is used to solve mazes so I'm trying that route...

Right now I just added a same size matrix to track if that spot has been visited or not. I'm trying to just figure out a way. Given an initial spot, to see if I can traverse to the top row using recursion..

I know this is wrong, someone's help can guide me. I have stuck right now and I'm kinda frustrated. This is what i got so far

private boolean [][] grid;
private boolean [][] visited;
private int size;

public boolean isFull(int i, int j)
{
    int row = i-1;
    int col = j-1;


    //base cases        
    if(row < 0 || row > size || col < 0 || col > size) {
        throw new IndexOutOfBoundsException("Out of Bounds Exception");
    }

    if(row == 0) {
        return true;
    }

    if(visited[row][col]) {
        return false;
    }

    visited[row][col] = true;

    //top
    isFull(row, col-1);
    //bot
    isFull(row, col+1);
    //left
    isFull(row-1, col);
    //right
    isFull(row+1, col);

    return false;
}

Upvotes: 0

Views: 1325

Answers (1)

lambda
lambda

Reputation: 1235

There is this website that uses java and a recursive method to check if a grid percolates. There is another way to check by using the "Union Find" algorithm:

/*
    To start and for convenience, set each elements's
    id to its own index value
*/

//number of elements to test
int n; 

int[] treeSize = new int[n];
int[] id = new int[n];
for(int i = 0; i < n; i++){
    id[i] = i;
    treeSize[i] = 1;
}

void makeUnion(int p, int q){
    /*
       Connect smaller tree to the bigger one by
       making root of the smaller tree the child of
       the root of the bigger tree.
    */
    int pRoot = getRoot(p);
    int qRoot = getRoot(q);

    treeSize[pRoot] < treeSize[qRoot] ?
      id[pRoot] = qRoot, treeSize[qRoot] += treeSize[pRoot] :
      id[qRoot] = pRoot, treeSize[pRoot] += treeSize[qRoot] ;
}

bool connected(int p, int q){
  return getRoot(p) == getRoot(q);
 }

int getRoot(int i){
   /*
     Transverse through parent
     pointers in the tree
     until root is reached
   */
   while(i != id[i]){         //check if root
      id[i] = id[ id[i] ];  //flatten tree a bit(path compression by 1/2) points to grand-parent now
      i = id[i];                          //move up one level
   }
   return i;
}

You iterate through the entire grid and use makeUnion to connect two spots if they are open and adjacent and use connected to check if bottom and top are connected.

Upvotes: 1

Related Questions