490. The Maze

Problem Description

In this problem, we're given a 2D array that represents a maze, where 0s represent empty spaces and 1s represent walls. The maze is surrounded by walls on all borders. A ball can roll through the maze, but it only stops moving when it hits a wall. Once it's stopped, it can then be rolled again in any of the four cardinal directions (up, down, left, right). The goal is to determine if there is a way to move the ball from its start position to a specified destination by only rolling it in such a way that it stops at the destination. The start position and destination are given as [row, column] coordinates. The problem asks us to return true if the ball can reach the destination and stop there, and false otherwise.

Intuition

The solution to this problem involves exploring the maze to find if there is a path to the destination. Exploring a maze is a classic problem that is usually solved using graph traversal algorithms like Depth-First Search (DFS) or Breadth-First Search (BFS). The intuition behind using BFS in this particular problem is that we want to explore all possible paths where the ball can roll until it hits a wall.

The main idea is to simulate the rolling of the ball. We start at the initial position and roll the ball in all possible directions until it hits a wall. Once it comes to a stop, we check if the current stopping point is the destination. If it's not, we treat this stopping point as a new start point and continue to roll the ball in all four directions. We repeat this process until we either reach the destination or all possible paths have been explored without reaching it.

We need to keep track of the positions we have already visited to prevent infinite loops. This is because without tracking, we might keep revisiting the same positions over and over again. For this purpose, we use a set to store visited positions.

By using BFS with a queue and a visited set, we can systematically explore the maze and check if a path to the destination exists.

Learn more about Depth-First Search and Breadth-First Search patterns.

Solution Approach

The implementation of the aforementioned BFS approach is straightforward. To explain how the solution works, let's break it down step by step:

1. Queue Initialization: We initialize a queue q for the BFS with the starting position of the ball. This queue will be used to store the positions from where we need to continue exploring further.

2. Visited Set: To keep track of the positions we have visited so far to avoid re-processing, we initialize a set vis.

3. BFS Loop: We enter a loop to process each element in the queue until it's empty, which means we've exhausted all possible movements. For each position taken from the queue: a. We calculate potential new positions by moving the ball in all four possible directions until it hits a wall. b. For each of the four directions, we ensure that the movement is within the bounds of the maze and we are moving into empty space (0). c. As soon as the ball stops due to hitting a wall, we check if the stopped position is the destination. If it is, we've found a path, and we return true. d. If the new stopped position is not the destination and hasn't been visited yet, we add it to the visited set and the queue for further exploration.

4. Directions Representation: The directions in which the ball can move are represented by the vectors [[0, -1], [0, 1], [-1, 0], [1, 0]], which correspond to left, right, up, and down movements, respectively.

5. Exploring Paths: For each position discovered, the loop continues exploring further by seeing where the ball can go next from these new positions, until it either reaches the destination or there are no more positions to explore (the queue becomes empty).

6. Return False: If the queue is exhausted without finding the destination, the function returns false, signifying that there is no path that leads to the destination.

The choice of BFS in this case is strategic, as it allows us to explore the maze level by level, considering the shortest paths first and ensuring that once we reach the destination, we've found the optimal solution (should one exist).

Here's the implementation as provided in the reference document:

1class Solution:
2    def hasPath(
3        self, maze: List[List[int]], start: List[int], destination: List[int]
4    ) -> bool:
5        m, n = len(maze), len(maze[0])
6        q = deque([start])
7        rs, cs = start
8        vis = {(rs, cs)}
9        while q:
10            i, j = q.popleft()
11            for a, b in [[0, -1], [0, 1], [-1, 0], [1, 0]]:
12                x, y = i, j
13                while 0 <= x + a < m and 0 <= y + b < n and maze[x + a][y + b] == 0:
14                    x, y = x + a, y + b
15                if [x, y] == destination:
16                    return True
17                if (x, y) not in vis:
18                    vis.add((x, y))
19                    q.append((x, y))
20        return False

This code clearly follows the BFS paradigm, and it allows us to see a practical implementation of the intuition discussed earlier.

Example Walkthrough

Let's take an example maze and walk through the solution using the BFS approach detailed in the content above.

Suppose we have the following 2D maze where S is the start position, D is the destination, 0 represents open space, and 1 represents a wall:

11 1 1 1 1
21 0 0 0 1
31 0 1 0 1
41 S 1 D 1
51 1 1 1 1

The start position is marked as [3, 1] and the destination is [3, 3]. We want to find if there's a path for the ball to roll from S to D.

1. Queue Initialization: Initialize the queue with the start position (3, 1).

2. Visited Set: Initialize the visited set and add the start position to it.

3. BFS Loop: Now, we start processing the position (3, 1) and we need to explore all four directions. We'll simulate the rolling of the ball until it hits a wall:

   • Rolling left is not an option since (3, 0) is a wall.
   • Rolling right ends up at (3, 2), just before the wall.
   • Rolling up isn't possible due to hitting a wall immediately.
   • Rolling down hits a wall immediately.

4. We then mark (3, 2) as visited and add it to the queue if it's not already visited. In this case, it's a new position so we add it.

5. The queue now has (3, 2), and we pick this and repeat the process. Rolling right from (3, 2) makes the ball stop at (3, 3), which is our destination D.

6. Once we hit the destination, we return True, indicating that there is indeed a path from S to D.

If we continue the loop without finding the destination, we will eventually run out of positions to check, which would compel us to return False, indicating there's no such path. However, in this example, since we did reach the destination, we successfully exit the loop with the correct outcome.

Solution Implementation

Time and Space Complexity

The given code is an implementation of the Breadth-First Search (BFS) algorithm, which is used to determine whether there is a path from the start to the destination in a given maze using possible movements up, down, left, or right. It stops movement in one direction when it hits a wall or the edge of the maze.

Time Complexity

The time complexity of this function is O(m * n), where m is the number of rows, and n is the number of columns in the maze. This is because, in the worst case, the algorithm may explore each cell in the maze once. Each cell is added to the queue only once, and each roll in one of four directions continues until it hits a wall, but the rolling action does not increase the total number of cells visited. Each possible space is processed once, so at most, the algorithm will perform m * n operations.

Space Complexity

The space complexity of the function is also O(m * n). This is due to the storage required for the visited set vis, which in the worst case may contain every cell in the maze. Moreover, the queue q may also store a significant number of positions although not more than m * n. However since we only store each cell at most once, the space complexity remains O(m * n) overall.

Learn more about how to find time and space complexity quickly using problem constraints.