"Finding the Shortest Path in a Maze"

Problem

Given an input of 2D array representing a maze, find the shortest path from the top-left corner of the maze to the bottom-right corner.
Example input:
[[0,1,0,0,0],
 [0,1,0,1,0],
 [0,0,0,1,0],
 [1,1,1,1,0],
 [0,0,0,0,0]]
Example output:
[[0,1,0,0,0],
 [0,1,0,1,0],
 [0,0,0,1,0],
 [1,1,1,1,0],
 [0,0,0,0,0]]

Solution

This solution is in Python. Our A.I. can create solutions in multiple languages.

kayakane

# Solution:
# This is a BFS problem.
# We start from the top left corner and add it to the queue.
# We then pop the first element from the queue and add it to the visited set.
# We then check if the element is the bottom right corner. If it is, we return the path.
# If it is not, we check all the neighbors of the element and add them to the queue if they are not in the visited set.
# We then repeat the process until we find the bottom right corner.
# The time complexity is O(n) where n is the number of elements in the maze.
# The space complexity is O(n) where n is the number of elements in the maze.

from collections import deque

def find_shortest_path(maze):
    if not maze:
        return None
    queue = deque()
    visited = set()
    queue.append((0, 0, [(0, 0)]))
    while queue:
        x, y, path = queue.popleft()
        if (x, y) in visited:
            continue
        visited .add((x, y))
        if x == len(maze) - 1 and y == len(maze[0]) - 1:
            return path
        for i, j in [(x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1)]:
            if 0 <= i < len(maze) and 0 <= j < len(maze[0]) and maze[i][j] == 0 and (i, j) not in visited:
                queue.append((i, j, path + [(i, j)]))
    return None

maze = [[0,1,0,0,0],
        [0,1,0,1,0],
        [0,0,0,1,0],
        [1,1,1,1,0],
        [0,0,0,0,0]]
print(find_shortest_path(maze))