490. The Maze - Detailed Explanation

Problem Statement

Problem Description

You are given a maze represented by a 2D grid. In the maze:

0 represents an empty space.
1 represents a wall.

A ball is placed in the maze at a start position. It can roll in four directions: up, down, left, or right. However, once it starts moving, it will continue rolling in that direction until it hits a wall (or the boundary of the maze), at which point it stops immediately before the wall. From this stopping position, it can choose a new direction to roll. Your task is to determine if the ball can stop exactly at the destination position.

Example Inputs/Outputs and Explanations

Example 1:

Input:

Maze:

[
  [0, 0, 1, 0, 0],
  [0, 0, 0, 0, 0],
  [0, 0, 0, 1, 0],
  [1, 1, 0, 1, 1],
  [0, 0, 0, 0, 0]
]

Start: [0, 4]
Destination: [4, 4]

Output: true
Explanation:
The ball can roll left, then down, left, down, right, and down, eventually stopping exactly at [4, 4].

Example 2:

Input:

Maze:

[
  [0, 0, 1, 0, 0],
  [0, 0, 0, 0, 0],
  [0, 0, 0, 1, 0],
  [1, 1, 0, 1, 1],
  [0, 0, 0, 0, 0]
]

Start: [0, 4]
Destination: [3, 2]

Output: false
Explanation:
No matter how the ball rolls, it cannot come to rest at [3, 2].

Example 3:

Input:

Maze:

[
  [0, 1, 0, 0, 0],
  [0, 0, 0, 1, 0],
  [1, 1, 0, 1, 0],
  [0, 0, 0, 0, 0],
  [0, 1, 1, 0, 0]
]

Start: [0, 0]
Destination: [4, 4]

Output: true
Explanation:
By carefully choosing directions and rolling until it stops, the ball can reach [4, 4].

Constraints

The maze is a 2D array containing only 0s and 1s.
Maze dimensions can be up to 100 x 100.
The ball continues rolling in a chosen direction until it hits a wall.
The start and destination positions are valid positions within the maze.

Hints to Approach the Problem

Hint 1: Think about how the ball moves. When you choose a direction, the ball does not stop at the next cell—it keeps rolling until it meets a wall.
Hint 2: Use graph traversal algorithms like DFS or BFS to explore all possible positions where the ball can come to a stop.
Hint 3: Always mark positions that have been visited to avoid cycles and unnecessary reprocessing.

Approaches

Approach 1: Brute Force (Naive DFS without Optimization)

Idea:
Use recursion to try every possible path from the start position. For each move, simulate the ball rolling until it stops.
Pitfall:
Without tracking visited states, the same positions can be revisited repeatedly, leading to an exponential number of recursive calls and possible infinite loops.

Approach 2: Optimized DFS/BFS with Visited Tracking

Idea:
Use either DFS or BFS to explore the maze. At each stopping point, try all four directions, and simulate the ball rolling until it hits a wall.
Key Points:
- Simulation: For each direction, move the ball step-by-step until it cannot move further.
- Visited Array: Use a 2D boolean array to mark cells where the ball has already stopped.
- Search Structure: A stack (for DFS) or a queue (for BFS) to manage the cells to be processed.
Benefits:
Marking visited positions prevents processing the same state multiple times and ensures that the algorithm terminates efficiently.

Code Implementations

Python Code

Python3

. . . .

Java Code

Java

. . . .

Complexity Analysis

Time Complexity

Optimal DFS/BFS Approach:
In the worst case, every cell in the maze may be visited. For each cell, you simulate rolling in four directions, and each roll can traverse up to O(max(m, n)) cells.
- Time Complexity: O(m * n * max(m, n))

Space Complexity

Space:
A visited matrix of size m × n is maintained along with a stack/queue.
- Space Complexity: O(m * n)

Step-by-Step Walkthrough

Initialization:
- Start at the given start position.
- Create a visited matrix to track cells where the ball has already come to rest.
- Initialize a stack (or queue) with the start position.
Explore Directions:
- For the current cell, try moving in all four directions (up, down, left, right).
Rolling Simulation:
- For each direction, simulate the ball rolling continuously until it can no longer move (either due to a wall or boundary).
- The ball's new position is the last valid cell before the wall.
Destination Check:
- After each roll, check if the ball has reached the destination.
- If yes, return true.
Mark and Continue:
- If the new cell is not visited, mark it as visited and add it to the stack/queue.
- Continue until the stack/queue is empty.
Conclusion:
- If the destination is never reached, return false.

Visual Example

Consider the following maze:

Start at (0, 4):
- Rolling Left:
  The ball rolls left until it is blocked by a wall and stops at (0, 1).
- Rolling Down from (0, 1):
  The ball continues to roll down until it hits a wall, eventually finding another stopping point.
- Repeating this process:
  The ball explores the maze until, if possible, it eventually reaches the destination (4, 4).

Additional Sections

Common Mistakes

Incorrect Rolling Simulation:
Stopping the ball too early instead of rolling until it hits a wall.
Not Marking Visited Cells:
Failing to mark cells as visited may cause infinite loops or redundant calculations.
Boundary Checks:
Neglecting to properly check the maze boundaries during rolling.

Edge Cases

Start Equals Destination:
If the start position is the same as the destination, the answer should be true.
No Valid Moves:
The ball may be trapped by walls with no valid directions to roll.
Empty or Single-Cell Maze:
Handle cases where the maze is minimal in size.

The Maze II:
Find the shortest distance for the ball to reach the destination.
The Maze III:
Determine the lexicographically smallest path for the ball to reach the destination.
Shortest Path in a Binary Matrix:
A different maze pathfinding problem with varied movement rules.