# Lee Algorithm|Shortest Path in a Maze

Feb. 28, 2021 17298

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 =
[ 0  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()

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

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
#include <bits/stdc++.h>
using namespace std;
#define ROW 5
#define COL 5

//To store cell cordinates
struct Cell
{
int x;
int y;
};

// Declaring Queue to be used in BFS
struct queueNode
{
Cell pt; // Cell cordinates
int dist; // Cell's distance of from the source
};

// Check whether given cell(row,col) is a valid cell or not
bool checkValid(int row, int col)
{
return ((row >= 0) && (row < ROW) &&	(col >= 0) && (col < COL));
}

// These arrays show the 4 possible movement from a cell
int rowNum[] = {-1, 0, 0, 1};
int colNum[] = {0, -1, 1, 0};

// Function to find the shortest path between source cell and destination cell.
int bfsLee(int mat[][COL], Cell src, Cell dest)
{
// Checking if source and destination cell have value 1
if (!mat[src.x][src.y] || !mat[dest.x][dest.y])
return -1;

bool visited[ROW][COL];
memset(visited, false, sizeof visited);

// Mark the source cell as visited
visited[src.x][src.y] = true;

// Create a queue for BFS
queue<queueNode> q;

// Distance of source cell is 0
queueNode s = {src, 0};
q.push(s); // Enqueue source cell

// Performing BFS starting from source cell
while (!q.empty())
{
queueNode curr = q.front();
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.pop();
// 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] &&
!visited[row][col])
{

visited[row][col] = true;
queueNode Adjcell = { {row, col},
curr.dist + 1 };
}
}
}

// Return -1 if destination cannot be reached
return -1;
}

// Driver program to test above function
int main()
{
int mat[ROW][COL] =
{
{ 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 = {0, 0};
Cell dest = {2, 1};

int dist = bfsLee(mat, source, dest);

if (dist != -1)
cout<< "Length of the Shortest Path is "<<dist ;
else
cout<< "Shortest Path doesn't exist";

return 0;
}

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 );
}
}
}

// 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");
}
}

from collections import deque
ROW = 5
COL = 5

# To store cell cordinates
class Cell:
def __init__(self,x: int, y: int):
self.x = x
self.y = y

# Declaring Queue to be used in BFS
class queueNode:
def __init__(self,pt: Cell, dist: int):
self.pt = pt # Cell coordinates
self.dist = dist # Cell's distance from the source

# Check whether given cell(row,col) is a valid cell or not
def checkValid(row: int, col: int):
return ((row >= 0) and (row < ROW) and (col >= 0) and (col < COL))

# These arrays show the 4 possible movement from a cell
rowNum = [-1, 0, 0, 1]
colNum = [0, -1, 1, 0]

# Function to find the shortest path between source cell and destination cell.
def bfsLee(mat, src: Cell, dest: Cell):

# Checking if source and destination cell have value 1
if mat[src.x][src.y]!=1 or mat[dest.x][dest.y]!=1:
return -1

visited = [[False for i in range(COL)]
for j in range(ROW)]

# Mark the source cell as visited
visited[src.x][src.y] = True

# Create a queue for BFS
q = deque()

# Distance of source cell is 0
s = queueNode(src,0)
q.append(s) # Enqueue source cell

# Perform BFS starting from source cell
while q:

curr = q.popleft() # Dequeue the front cell

# If we have reached the destination cell, return the final distance
pt = curr.pt
if pt.x == dest.x and pt.y == dest.y:
return curr.dist

# Otherwise enqueue its adjacent cells with value 1
for i in range(4):
row = pt.x + rowNum[i]
col = pt.y + colNum[i]

# Enqueue valid adjacent cell that is not visited
if (checkValid(row,col) and
mat[row][col] == 1 and
not visited[row][col]):
visited[row][col] = True
curr.dist+1)

# Return -1 if destination cannot be reached
return -1

# Driver code
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 ]]
source = Cell(0,0)
dest = Cell(2,1)

dist = bfsLee(mat,source,dest)

if dist!=-1:
print("Length of the Shortest Path is",dist)
else:
print("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.

Liked the post?
Zealous Learner.
Editor's Picks
0 COMMENT