Lee Algorithm|Shortest Path in a Maze

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:

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

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

Psuedocode

• 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

#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 };
				q.push(Adjcell);
			}
		}
	}

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

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
				Adjcell = queueNode(Cell(row,col),
									curr.dist+1)
				q.append(Adjcell)
	
	# 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:

Complexity Analysis

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.