Backtracking

  1. Rat in a Maze GFG
    Algo: 


  2. Shortest Path in a Binary Maze. This is solved using Lee Algorithm which is a basic BFS. GFG Link
    Algo: The idea is inspired from Lee algorithm and uses BFS.

    1. We start from the source cell and calls BFS procedure.
    2. We maintain a queue to store the coordinates of the matrix and initialize it with the source cell.
    3. We also maintain a Boolean array visited of same size as our input matrix and initialize all its elements to false.
      1. We LOOP till queue is not empty
      2. Dequeue front cell from the queue
      3. Return if the destination coordinates have reached.
      4. For each of its four adjacent cells, if the value is 1 and they are not visited yet, we enqueue it in the queue and also mark them as visited.

    If we are at a cell and want to generate the cells around it (not the diagonal one, only those on left, right, up, down) check the code how to efficiently do that.
    int rowNum[] = {-1, 0, 0, 1};
    int colNum[]   = {0, -1, 1, 0};


  3. Count the number of path in a maze. GFG
    Algo:  We build upon the logic to find the path from in a maze. We we the same logic to navigate the maze. When we reach the destination generally we end the program. But here we will keep a counter when we reach the final dest. Then we return false and start backtracking to find an alternate path. This way all the paths will be discovered. Code
Advertisements

Leave a Reply

Please log in using one of these methods to post your comment:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s