Teaching Kids Programming – Escape Maze by Breadth First Search Algorithm

Teaching Kids Programming: Videos on Data Structures and Algorithms

You are given a two dimensional integer matrix, representing a maze where 0 is an empty cell, and 1 is a wall. Given that you start at matrix[0][0], return the minimum number of squares it would take to get to matrix[R – 1][C – 1] (where R and C are the number of rows and columns in the matrix).

If it’s not possible, return -1.

Constraints
n, m ≤ 250 where n and m are the number of rows and columns in matrix
Example 1
Input

1 2 3 4 5

matrix = [     [0, 1, 0],     [0, 0, 1],     [0, 0, 0] ]

matrix = [
    [0, 1, 0],
    [0, 0, 1],
    [0, 0, 0]
]

Output
5
Explanation
We can take this path:
@ 1 0
@ @ 1
0 @ @
Example 2
Input

1 2 3 4 5

matrix = [     [0, 0, 0],     [0, 0, 0],     [0, 0, 1] ]

matrix = [
    [0, 0, 0],
    [0, 0, 0],
    [0, 0, 1]
]

Output
-1
Explanation
We can’t reach the bottom right because it’s blocked.

Breadth First Search Algorithm to Escape the Maze

If the top left and bottom right corner is wall piece, we know it is impossible – thus return -1 immediately.

Otherwise, we can perform a Breadth First Search (BFS) algorithm, only expanding to pixels that are not walls. Also, we have to avoid re-visiting the same pixels by using a hash set.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

class Solution:
    def escapeMazeBFS(self, matrix):
        if not matrix:
            return -1
        rows = len(matrix)
        cols = len(matrix[0])
        if matrix[0][0] == 1 or matrix[-1][-1] == 1:
            return -1
        q = deque([(0, 0, 1)])
        vis = set()
        while q:
            r, c, s = q.popleft()
            if r == rows - 1 and c == cols - 1:
                return s
            if (r, c) in vis:
                continue
            vis.add((r, c))
            for dr, dc in [(1, 0), (0, 1), (-1, 0), (0, -1)]:
                nr = r + dr
                nc = c + dc
                if 0 <= nr < rows and 0 <= nc < cols and matrix[nr][nc] != 1:
                    q.append((nr, nc, s + 1))
        return -1

class Solution:
    def escapeMazeBFS(self, matrix):
        if not matrix:
            return -1
        rows = len(matrix)
        cols = len(matrix[0])
        if matrix[0][0] == 1 or matrix[-1][-1] == 1:
            return -1
        q = deque([(0, 0, 1)])
        vis = set()
        while q:
            r, c, s = q.popleft()
            if r == rows - 1 and c == cols - 1:
                return s
            if (r, c) in vis:
                continue
            vis.add((r, c))
            for dr, dc in [(1, 0), (0, 1), (-1, 0), (0, -1)]:
                nr = r + dr
                nc = c + dc
                if 0 <= nr < rows and 0 <= nc < cols and matrix[nr][nc] != 1:
                    q.append((nr, nc, s + 1))
        return -1

The time complexity is O(RC) where R and C are the dimensions of the maze. And space complexity is O(RC) as well as we are using a queue to implement the BFS and a hash set to store the pixels that we have visited.

See also: Compute the Sequential Digits within a Range using DFS, BFS, or Bruteforce Algorithms

–EOF (The Ultimate Computing & Technology Blog) —