Problem Description

Given a maze represented as a 2D grid:

The objective is to find a valid path from S to E.

Example maze:

1
2
3
4
5

S 0 1 0 0
0 0 1 0 1
1 0 0 0 1
1 1 1 0 0
1 1 1 1 E

Python representation:

1
2
3
4
5
6
7
8
9
10

maze = [
    ['S', 0, 1, 0, 0],
    [0,   0, 1, 0, 1],
    [1,   0, 0, 0, 1],
    [1,   1, 1, 0, 0],
    [1,   1, 1, 1, 'E']
]

start = (0, 0)
end = (4, 4)

Solution 1: Depth-First Search (DFS)

Idea

Depth-First Search explores one path as deeply as possible before backtracking.

Algorithm:

  1. Push the starting cell onto a stack.
  2. Mark visited cells.
  3. Pop the top cell.
  4. If it is the destination, return the path.
  5. Push all valid neighboring cells.
  6. Repeat until the stack is empty.

Characteristics:

Python Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54

def dfs(maze, start, end):
    rows = len(maze)
    cols = len(maze[0])

    stack = [(start, [start])]
    visited = set()

    directions = [
        (-1, 0),   # Up
        (1, 0),    # Down
        (0, -1),   # Left
        (0, 1)     # Right
    ]

    while stack:
        (x, y), path = stack.pop()

        if (x, y) == end:
            return path

        if (x, y) in visited:
            continue

        visited.add((x, y))

        for dx, dy in directions:
            nx = x + dx
            ny = y + dy

            if (0 <= nx < rows and
                0 <= ny < cols and
                maze[nx][ny] != 1 and
                (nx, ny) not in visited):

                stack.append(((nx, ny), path + [(nx, ny)]))

    return None


maze = [
    ['S', 0, 1, 0, 0],
    [0,   0, 1, 0, 1],
    [1,   0, 0, 0, 1],
    [1,   1, 1, 0, 0],
    [1,   1, 1, 1, 'E']
]

start = (0, 0)
end = (4, 4)

path = dfs(maze, start, end)

print("DFS Path:")
print(path)

Solution 2: Breadth-First Search (BFS)

Idea

Breadth-First Search explores the maze level by level.

Algorithm:

  1. Enqueue the starting cell.
  2. Mark visited cells.
  3. Dequeue the front cell.
  4. If it is the destination, return the path.
  5. Enqueue all valid neighboring cells.
  6. Continue until the queue becomes empty.

Characteristics:

Python Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59

from collections import deque


def bfs(maze, start, end):
    rows = len(maze)
    cols = len(maze[0])

    queue = deque()
    queue.append((start, [start]))

    visited = set()

    directions = [
        (-1, 0),
        (1, 0),
        (0, -1),
        (0, 1)
    ]

    while queue:
        (x, y), path = queue.popleft()

        if (x, y) == end:
            return path

        if (x, y) in visited:
            continue

        visited.add((x, y))

        for dx, dy in directions:
            nx = x + dx
            ny = y + dy

            if (0 <= nx < rows and
                0 <= ny < cols and
                maze[nx][ny] != 1 and
                (nx, ny) not in visited):

                queue.append(((nx, ny), path + [(nx, ny)]))

    return None


maze = [
    ['S', 0, 1, 0, 0],
    [0,   0, 1, 0, 1],
    [1,   0, 0, 0, 1],
    [1,   1, 1, 0, 0],
    [1,   1,   1, 1, 'E']
]

start = (0, 0)
end = (4, 4)

path = bfs(maze, start, end)

print("BFS Path:")
print(path)

Visualizing the Solution Path

1
2
3
4
5
6
7
8
9
10
11
12
13

def print_path(maze, path):
    result = [row[:] for row in maze]

    for x, y in path:
        if result[x][y] == 0:
            result[x][y] = '*'

    for row in result:
        print(*row)


path = bfs(maze, start, end)
print_path(maze, path)

Using

1
2
3
4
5
6
7
8
9
10
11
12
13
14

maze = [
    ['S', 0, 1, 0, 0],
    [0,   0, 1, 0, 1],
    [1,   0, 0, 0, 1],
    [1,   1, 1, 0, 0],
    [1,   1, 1, 1, 'E']
]

start = (0, 0)
end = (4, 4)

path = dfs(maze, start, end)

print_path(maze, path)

Output:

1
2
3
4
5

S * 1 0 0
0 * 1 0 1
1 * * * 1
1 1 1 * *
1 1 1 1 E

Complexity Analysis

Assume the maze has:

Number of cells:

\[V = R × C\]

Each cell has at most four neighbors.

Algorithm Time Complexity Space Complexity
DFS O(R × C) O(R × C)
BFS O(R × C) O(R × C)