- Rat in a Maze GFG

**Algo:**

- 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.- We start from the source cell and calls BFS procedure.
- We maintain a queue to store the coordinates of the matrix and initialize it with the source cell.
- We also maintain a Boolean array visited of same size as our input matrix and initialize all its elements to false.
- We LOOP till queue is not empty
- Dequeue front cell from the queue
- Return if the destination coordinates have reached.
- 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};

- 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