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