# 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