Maze routing problems are one of the most interesting programming problems out there. There are many possible ways to solve maze routing problems and today we shall discuss one such approach using the __Lee Algorithm to find the shortest path in a maze__.

## Problem Description

In this problem, we are provided with a maze in the form of a binary rectangular matrix and our task is to** find the shortest path between a given source cell to a destination cell**. The maze is represented as a MxN matrix where each element can either be 0 or 1. A path can be created out of a cell only if its value is 1. At any given time, we can only move one step in one of the 4 directions. Thus, the valid steps are:

**Move Up: (x, y) ——> (x – 1, y)Move Left: (x, y) ——> (x, y – 1)
Move Down: (x, y) ——> (x + 1, y)Move Right: (x, y) ——> (x, y + 1)**

Let us see an example to better understand the problem statement:

Input:

matrix =

[ **1 **0 1 1 1

**1 **0 1 0 1

**1 1 **1 0 1

0 0 0 0 1

1 1 1 0 1 ]

Source cell = {0, 0}

Destination cell = {2, 1}

Output:

Length of the shortest path is 3

## Approach

In this problem we shall use the Lee Algorithm that is based on the breadth-first-search (BFS) procedure. Here we use a combination of a queue and a matrix to identify which cell has been visited and by repeating this process again and again, we finally find the shortest path from source cell to the destination cell.

The BFS technique is best suited to find the shortest path because it doesn’t consider a single path at once, rather it considers all the paths starting from the source and moves ahead one unit in all those paths at the same time. All this ensures that the first time when the destination cell is visited, it is the shortest path.

## Algorithm

1. Create an empty queue to store the coordinates of the matrix and initialize it with the source cell having a distance of 0 from the source, marking it as visited.

2. Starting from the source cell, call the BFS procedure.

3. Initialize a boolean array of the same size as input matrix and all values set to false. This is used to store the visited status of a coordinate.

4. Run a loop till the queue is empty

Dequeue front cell from the queue

Return if the destination cell is reached

Otherwise, For each of the four adjacent cells of a current cell, if the cell value is 1 and they are un-visited, enqueue the cells and mark them as visited.

5. If all queue elements are processed and destination is not reached, return false.

## Psuedocode

Initialize movement arrays=>

rowNum := [-1, 0, 0, 1], colNum := [0, -1, 1, 0]

bfsLee(mat, src, dest)

if mat[src.x][src.y]!=1 or mat[dest.x][dest.y]!=1, then

return -1

Initialize matrix: visited[Row][Col]:= False

visited[src.x][src.y] := True

Initialize empty queue: q := Queue()

q.add(src)

while q is not Empty, loop

curr := q.Pop()

pt := curr.coordinates

if pt.x = dest.x and pt.y = dest.y, then

return curr.distance

for i in 0 to 4

row := pt.x + rowNum[i]

col := pt.y + colNum[i]

if mat(row, col) is valid and mat(row,cell) = 1 and mat(row,cell) is not visited, then

visited[row][col] := True

q.add(current_Adjacent_Cell)

return -1

- In the above pseudocode, we first initialize two arrays
`rowNum`

and`colNum`

which help us in visiting all the four adjacent cells of the current cell by adding the value of these arrays to the current cell coordinates.

- In our method
`bfsLee()`

we firstly check whether the given source and destination cells are valid or not, i.e. their value is**1**. If either the source or destination is invalid, we return -1 as path can not be formed in that case. - If the given source and destination are proper, we initialize the visited matrix with all values set to
`False`

. We also initialize an empty queue (q) and then we add the source cell to this queue and mark it as visited. - After that we run a loop until our queue is completely empty and check for each node by popping it from the queue and then processing it. We store the coordinates of the current cell in a pointer and check if the coordinates are equal to our destination cell, then we
**return the distance**up to that pointer. If the destination is not reached, we check for all the adjacent cells using the`rowNum`

and`colNum`

arrays and add them to our queue if a path is possible through them and they are still not visited. In this way we are applying a BFS pattern by checking all possible paths from a current cell. - We repeat the above loop until our either the destination is reached or the queue is empty. If the queue becomes empty before the destination cell is visited, there is no path to reach the destination cell from the source cell and we
`return -1`

in that case.

Let us understand the working of the pseudocode better through an example:

## Code

- C/C++
- Java
- Python

```
import java.util.*;
class ShortestPathMaze
{
static int ROW = 5;
static int COL = 5;
// To store cell cordinates
static class Cell
{
int x;
int y;
public Cell(int x, int y)
{
this.x = x;
this.y = y;
}
};
// Declaring Queue to be used in BFS
static class queueNode
{
Cell pt; // Cell cordinates
int dist; // Cell's distance of from the source
public queueNode(Cell pt, int dist)
{
this.pt = pt;
this.dist = dist;
}
};
// Check whether given cell(row,col) is a valid cell or not
static boolean checkValid(int row, int col)
{
return ((row >= 0) && (row < ROW) && (col >= 0) && (col < COL));
}
// These arrays show the 4 possible movement from a cell
static int rowNum[] = {-1, 0, 0, 1};
static int colNum[] = {0, -1, 1, 0};
// Function to find the shortest path between source cell and destination cell
static int bfsLee(int mat[][], Cell src, Cell dest)
{
// Checking if source and destination cell have value 1
if (mat[src.x][src.y] != 1 || mat[dest.x][dest.y] != 1)
return -1;
boolean [][]visited = new boolean[ROW][COL];
// Mark the source cell as visited
visited[src.x][src.y] = true;
// Create a queue for BFS
Queue<queueNode> q = new LinkedList<>();
// Distance of source cell is 0
queueNode s = new queueNode(src, 0);
q.add(s); // Enqueue source cell
// Performing BFS starting from source cell
while (!q.isEmpty())
{
queueNode curr = q.peek();
Cell pt = curr.pt;
// If we have reached the destination cell, return the final distance
if (pt.x == dest.x && pt.y == dest.y)
return curr.dist;
q.remove();
// Otherwise enqueue its adjacent cells with value 1
for (int i = 0; i < 4; i++)
{
int row = pt.x + rowNum[i];
int col = pt.y + colNum[i];
// Enqueue valid adjacent cell that is not visited
if (checkValid(row, col) &&
mat[row][col] == 1 &&
!visited[row][col])
{
visited[row][col] = true;
queueNode Adjcell = new queueNode
(new Cell(row, col),
curr.dist + 1 );
q.add(Adjcell);
}
}
}
// Return -1 if destination cannot be reached
return -1;
}
// Driver Code
public static void main(String[] args)
{
int mat[][] = {{ 1, 0, 1, 1, 1 },
{ 1, 0, 1, 0, 1 },
{ 1, 1, 1, 0, 1 },
{ 0, 0, 0, 0, 1 },
{ 1, 1, 1, 0, 1 }};
Cell source = new Cell(0, 0);
Cell dest = new Cell(2, 1);
int dist = bfsLee(mat, source, dest);
if (dist != -1)
System.out.println("Length of the Shortest Path is " + dist);
else
System.out.println("Shortest Path doesn't exist");
}
}
```

Output:

Length of the Shortest Path is 3

## Complexity Analysis

Approach | Time Complexity | Space Complexity |
---|---|---|

Lee Algorithm to find shortest path in a maze | O(MxN) | O(MxN) |

The above solution traverses each cell of the matrix one by one in a BFS manner until our destination cell is reached or there is no path remaining. All this process leads to a **O(MxN)** time complexity where `M`

and `N`

are the dimensions of the matrix. Also, since we require an additional MxN matrix to store the visited status of cells, the space complexity is also **O(MxN)**.

In this way, we have learnt how to find shortest path between two points in a maze using the Lee Algorithm.