🎓 Top 15 Udemy Courses (80-90% Discount): My Udemy Courses - Ramesh Fadatare — All my Udemy courses are real-time and project oriented courses.
▶️ Subscribe to My YouTube Channel (178K+ subscribers): Java Guides on YouTube
▶️ For AI, ChatGPT, Web, Tech, and Generative AI, subscribe to another channel: Ramesh Fadatare on YouTube
1. Introduction
Finding the shortest path in a maze is a classic problem of computer science. The problem can be solved using various algorithms, but one of the most intuitive methods is the Breadth-First Search (BFS). In this tutorial, we will use BFS to find the shortest path in a maze represented as a 2D matrix.
2. Program Overview
Our Python program will:
1. Represent the maze as a 2D list where 0 is an open path and 1 represents a wall.
2. Implement BFS to find the shortest path from a given start point to an endpoint.
3. Return the shortest path or notify if no path exists.
3. Code Program
from collections import deque
def is_valid_move(maze, visited, x, y):
"""Check if a move is valid."""
return 0 <= x < len(maze) and 0 <= y < len(maze[0]) and not maze[x][y] and not visited[x][y]
def shortest_path_in_maze(maze, start, end):
"""Find the shortest path in the maze using BFS."""
if not maze or not maze[0]:
return None
rows, cols = len(maze), len(maze[0])
visited = [[False for _ in range(cols)] for _ in range(rows)]
# Each element in the queue will be a tuple containing cell coordinates and its distance from the start
queue = deque([(start, 0)])
visited[start[0]][start[1]] = True
# Possible moves in the maze: Up, Down, Left, Right
moves = [(-1, 0), (1, 0), (0, -1), (0, 1)]
while queue:
(x, y), dist = queue.popleft()
# If this point is the end, return the distance (shortest path length)
if (x, y) == end:
return dist
# Check all possible moves
for dx, dy in moves:
new_x, new_y = x + dx, y + dy
if is_valid_move(maze, visited, new_x, new_y):
visited[new_x][new_y] = True
queue.append(((new_x, new_y), dist + 1))
return None
# Sample maze: 0 is open path, 1 is wall
maze = [
[0, 1, 0, 0, 0],
[0, 1, 0, 1, 0],
[0, 0, 0, 1, 0],
[0, 1, 1, 1, 0],
[0, 0, 0, 0, 0]
]
start_point = (0, 0)
end_point = (4, 4)
print(f"Shortest path length: {shortest_path_in_maze(maze, start_point, end_point)}")
Output:
Shortest path length: 8
4. Step By Step Explanation
1. We start by defining a helper function is_valid_move that checks if a move is valid given the maze and visited nodes.
2. The main function shortest_path_in_maze initializes a visited matrix and sets up the BFS using a queue.
3. BFS works by exploring all possible moves at a current level before moving on to the next level. Thus, the first time we encounter the endpoint, we are guaranteed to have found the shortest path.
4. For each point, we check all potential moves (up, down, left, right). If the move is valid and leads to a solution, the function returns the length of the shortest path.
5. If there is no solution, the function will return None.
This approach ensures that we find the shortest path in the maze if it exists. Otherwise, we'll know that no solution is possible.
My Top and Bestseller Udemy Courses. The sale is going on with a 70 - 80% discount. The discount coupon has been added to each course below:
Build REST APIs with Spring Boot 4, Spring Security 7, and JWT
![[NEW] Learn Apache Maven with IntelliJ IDEA and Java 25](https://img-c.udemycdn.com/course/750x422/6852721_b512_2.jpg "[NEW] Learn Apache Maven with IntelliJ IDEA and Java 25")
[NEW] Learn Apache Maven with IntelliJ IDEA and Java 25
ChatGPT + Generative AI + Prompt Engineering for Beginners
Spring 7 and Spring Boot 4 for Beginners (Includes 8 Projects)
Available in Udemy for Business
Building Real-Time REST APIs with Spring Boot - Blog App
Available in Udemy for Business
Building Microservices with Spring Boot and Spring Cloud
Available in Udemy for Business
Java Full-Stack Developer Course with Spring Boot and React JS
Available in Udemy for Business
Build 5 Spring Boot Projects with Java: Line-by-Line Coding
Testing Spring Boot Application with JUnit and Mockito
Available in Udemy for Business
Spring Boot Thymeleaf Real-Time Web Application - Blog App
Available in Udemy for Business
Master Spring Data JPA with Hibernate
Available in Udemy for Business
Spring Boot + Apache Kafka Course - The Practical Guide
Available in Udemy for Business
Comments
Post a Comment
Leave Comment