Definition: The Lee algorithm is one feasible solution for maze routing problems based on a breadth-first search. It always gives an optimal solution, if one exists, but is slow and requires considerable memory. We will learn Lee Algorithm in Python by Solution to Maze Routing Problem.
The Lee algorithm has the properties of
a) always finding a path if one exists and
b) always finding the path with the lowest feasible cost.
In this article, only algorithms with these qualities will be addressed. Lee’s algorithm and its variants require the least amount of storage of any known algorithm. There is no cost matrix, nor are there any successor tables.
Step 1 – Make an empty queue and enqueue the source cell with a distance of 0 from the source (itself), marking it as visited.
Step 2 – Loop until the queue is empty.
- Dequeue the front node.
- If the popped node is the destination node, then return its distance.
- Otherwise, for each of four adjacent cells of the current cell, enqueue each valid cell with +1 distance and mark them as visited.
Step 3 – Return false if the destination is not reached after processing all queue nodes.
Click here to read more about the Lee algorithm on Wikipedia.
Maze Routing Problem with Lee Algorithm
In this problem, we will apply the Lee Algorithm, which is based on the breadth-first-search (BFS) procedure. In this case, we use a queue and a matrix to determine which cell has been visited, and we continue this procedure until we discover the shortest path from the source cell to the destination cell.
We are given a maze in the form of a binary rectangular matrix in this problem, and our objective is to identify the shortest path between a particular source cell and a destination cell. The maze is represented as an MxN matrix, with each element having a value of 0 or 1. A route may only be formed from a cell if its value is 1. We can only move one step in one of the four directions at a time.
Consequently, the following are appropriate steps:
Shift Up: (a, b) ——> (a – 1, b)
ShiftLeft: (a, b) ——> (a, b – 1)
Shift Down: (a, b) ——> (a + 1, b)
Shift Right: (a, b) ——> (a, b + 1)
Consider this example
Take the binary matrix shown below as an example. The shortest path from source to destination has a length of 5 if source and destination are (0, 0) and (3, 2), respectively.
[ 1 1 1 1 1 0 0 ]
[ 1 1 1 1 1 1 0 ]
[ 1 0 1 0 1 1 1 ]
[ 1 1 1 1 1 0 1 ]
[ 0 0 0 1 0 0 0 ]
[ 1 0 1 1 1 0 0 ]
[ 0 0 0 0 1 0 0 ]
Solving Maze Routing Problem with Lee Algorithm in Python
#importing libraries import sys from collections import deque # All four potential movements from a cell are listed here. row = [-1, 0, 0, 1] col = [0, -1, 1, 0] # Whether it is possible to move from the current position to position (row, col) # is determined by this function. If row, col is not in a legal location, # has a value of 0, or has already been visited, the method returns false. def Validate(matrix, visited, row, col): return (row >= 0) and (row < len(matrix)) and (col >= 0) and (col < len(matrix)) \ and matrix[row][col] == 1 and not visited[row][col] # Find the shortest path between sources and destinations in a matrix. def Shortest_Path(matrix, source, destination): # get source cell (i, j) i, j = source # get destination cell (x, y) x, y = destination # base case: invalid input if not matrix or len(matrix) == 0 or matrix[i][j] == 0 or matrix[x][y] == 0: return -1 # `M × N` matrix (M, N) = (len(matrix), len(matrix)) # construct a matrix to keep track of visited cells visited = [[False for x in range(N)] for y in range(M)] # create an empty queue q = deque() # mark the source cell as visited and enqueue the source node visited[i][j] = True # (i, j, dist) represents matrix cell coordinates, and their # minimum distance from the source q.append((i, j, 0)) # stores length of the longest path from source to destination min_dist = sys.maxsize # loop till queue is empty while q: # dequeue front node and process it (i, j, dist) = q.popleft() # (i, j) represents a current cell, and `dist` stores its # minimum distance from the source. # if the destination is found, update `min_dist` and stop if i == x and j == y: min_dist = dist break # check for all four possible movements from the current cell # and enqueue each valid movement for k in range(4): # check if it is possible to go to position # (i + row[k], j + col[k]) from current position if Validate(matrix, visited, i + row[k], j + col[k]): # mark next cell as visited and enqueue it visited[i + row[k]][j + col[k]] = True q.append((i + row[k], j + col[k], dist + 1)) if min_dist != sys.maxsize: return min_dist else: return -1 if __name__ == '__main__': matrix = [ [1, 1, 1, 1, 1, 0, 0, 1, 1, 1], [0, 1, 1, 1, 1, 1, 0, 1, 0, 1], [0, 0, 1, 0, 1, 1, 1, 0, 0, 1], [1, 0, 1, 1, 1, 0, 1, 1, 0, 1], [0, 0, 0, 1, 0, 0, 0, 1, 0, 1], [1, 0, 1, 1, 1, 0, 0, 1, 1, 0], [0, 0, 0, 0, 1, 0, 0, 1, 0, 1], [0, 1, 1, 1, 1, 1, 1, 1, 0, 0], [1, 1, 1, 1, 1, 0, 0, 1, 1, 1], [0, 0, 1, 0, 0, 1, 1, 0, 0, 1] ] source = (0, 0) destination = (3, 2) min_dist = Shortest_Path(matrix, source, destination) if min_dist != -1: print("The length of the shortest route between sources and destinations :- ", min_dist) else: print("The source cannot lead to the destination")
The above-mentioned solution iteratively travels through each matrix cell in a BFS fashion until it reaches our destination cell or runs out of paths. The complexity of the entire procedure is O(MxN), where M and N are the dimensions of the matrix. Additionally, the space complexity is O since we need a separate MxN matrix to hold the visited state of cells (MxN).
We have now learned how to use the Lee Algorithm in Python to determine the shortest path across a maze between any two places. Solution iteratively travels through each matrix cell in a BFS fashion until it reaches our destination cell or runs out of paths. The complexity of the entire procedure is O(MxN), where M and N are the dimensions of the matrix. Additionally, the space complexity is O since we need a separate MxN matrix to hold the visited state of cells (MxN).
What is Maze Routing Problem?
The maze routing problem is nothing but a problem that needs to be solved by any method and Lee Algorithm is considered the best algorithm to solve this problem.
What is Lee Algorithm?
The Lee algorithm is one feasible solution for maze routing problems based on a breadth-first search. It always gives an optimal solution, if one exists, but is slow and requires considerable memory – Wikipedia
- HackerRank Day 8 Solution in Python: Dictionaries and Maps
- HackerRank Day 7 Solution in Python: Arrays
- HackerRank Day 6 Solution in Python: Let’s review
- HackerRank Day 5 Solution in Python: Loops
- HackerRank Day 4 Solution in Python: Class vs Instance
- HackerRank Day 3 Solution in Python: Intro to Conditional Statements
- HackerRank Day 2 Solution in Python: Operators
- HackerRank Day 1 Solution in Python: Data Types
- HackerRank Day 0 Solution in Python: Hello World
- HackerRank Day 29 Solution in Python: Bitwise AND
- HackerRank Day 28 Solution in Python: RegEx, Patterns, and Intro to databases
- HackerRank Day 27 Solution in Python: Testing
- HackerRank Day 26 Solution in Python: Nested Logic
- HackerRank Day 25 Solution in Python: Running Time and Complexity
- HackerRank Day 24 Solution in Python: More Linked Lists
- HackerRank Day 23 Solution in Python: BST Level Order Traversal
- HackerRank Day 22 Solution in Python: Binary Search Trees
- Find Peak Element LeetCode 162
- HackerRank Day 20 Solution in Python: Sorting
- HackerRank Day 19 Solution in Python: Interfaces
- HackerRank Day 18 Solution in Python: Queues and Stacks
- HackerRank Day 17 Solution in Python: More Exceptions
- HackerRank Day 16 Solution: Exceptions – String to Integer
- Explained: Allocate minimum number of pages
- HackerRank Day 15 Solution in Python: Linked List
- Search a 2D matrix: leetcode 74
- Maximum Subarray Sum: Kadane’s Algorithm
- HackerRank Day 13 Solution in Python: Abstract Classes
- HackerRank Day 14 Solution in Python: Scope
- HackerRank Day 12 Solution in Python: Inheritance