Problem

There is a ball in a maze with empty spaces (represented as 0) and walls (represented as 1). The ball can go through the empty spaces by rolling up, down, left or right, but it won’t stop rolling until hitting a wall. When the ball stops, it could choose the next direction.

Given the m x n maze, the ball’s start position and the destination, where start = [startrow, startcol] and destination = [destinationrow, destinationcol], return true if the ball can stop at the destination, otherwise return false.

You may assume that the borders of the maze are all walls (see examples).

Examples

Example 1

$$ \Huge \begin{array}{|c|c|c|c|c|c|} \hline 🟨 & 🟨 & 🟨 & 🟨 & 🟨 & 🟨 & 🟨 \\ \hline 🟨 & & & 🟨 & \color{green} \triangleleft & ⚽️ & 🟨 \\ \hline 🟨 & & & \color{green} \triangleleft & \color{green} \triangledown & & 🟨 \\ \hline 🟨 & & & \color{green} \triangledown & 🟨 & & 🟨 \\ \hline 🟨 & 🟨 & 🟨 & \color{green} \triangledown & 🟨 & 🟨 & 🟨 \\ \hline 🟨 & & & \color{green} \triangledown & \color{green} \triangleright & 📍 & 🟨 \\ \hline 🟨 & 🟨 & 🟨 & 🟨 & 🟨 & 🟨 & 🟨 \\ \hline \end{array} $$

1
2
3
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: One possible way is : left -> down -> left -> down -> right -> down -> right.

Example 2

$$ \Huge \begin{array}{|c|c|c|c|c|c|c|} \hline 🟨 & 🟨 & 🟨 & 🟨 & 🟨 & 🟨 & 🟨 \\ \hline 🟨 & & & 🟨 & \color{red} \triangleleft & ⚽️ & 🟨 \\ \hline 🟨 & & & \color{red}\triangleleft & \color{red}\triangledown & & 🟨 \\ \hline 🟨 & & & \color{red}\triangledown & 🟨 & & 🟨 \\ \hline 🟨 & 🟨 & 🟨 & 📍 & 🟨 & 🟨 & 🟨 \\ \hline 🟨 & & & \color{red}\triangledown & & & 🟨 \\ \hline 🟨 & 🟨 & 🟨 & 🟨 & 🟨 & 🟨 & 🟨 \\ \hline \end{array} $$

1
2
3
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: There is no way for the ball to stop at the destination. Notice that you can pass through the destination but you cannot stop there.

Example 3

$$ \Huge \begin{array}{|c|c|c|c|c|c|c|} \hline 🟨 & 🟨 & 🟨 & 🟨 & 🟨 & 🟨 & 🟨 \\ \hline 🟨 & & 📍 & & & & 🟨 \\ \hline 🟨 & 🟨 & 🟨 & & & 🟨 & 🟨 \\ \hline 🟨 & & & & & & 🟨 \\ \hline 🟨 & & 🟨 & & & 🟨 & 🟨 \\ \hline 🟨 & & 🟨 & & ⚽️ & & 🟨 \\ \hline 🟨 & 🟨 & 🟨 & 🟨 & 🟨 & 🟨 & 🟨 \\ \hline \end{array} $$

1
2
Input: maze = [[0,0,0,0,0],[1,1,0,0,1],[0,0,0,0,0],[0,1,0,0,1],[0,1,0,0,0]], start = [4,3], destination = [0,1]
Output: false

Constraints

  • m == maze.length
  • n == maze[i].length
  • 1 <= m, n <= 100
  • maze[i][j] is 0 or 1.
  • start.length == 2
  • destination.length == 2
  • 0 <= startrow, destinationrow < m
  • 0 <= startcol, destinationcol < n
  • Both the ball and the destination exist in an empty space, and they will not be in the same position initially.
  • The maze contains at least 2 empty spaces.

Solution

Method 1 – Depth-First Search (DFS)

Intuition

The key idea is to use DFS to simulate the ball rolling in all four directions from the start position, but only consider the cells where the ball actually stops (the last empty cell before a wall). Treat those stopping cells as graph nodes and the one-roll transitions between them as edges; performing DFS (or BFS) over this graph G checks whether the destination is reachable as a stopping node. Therefore DFS returns true iff the destination node is reachable in G — which is exactly the condition “the ball can stop at the destination.”

Edge case (pass-through destination): if every time the ball passes through the destination it continues to a later stopping cell, then destination is not reachable as a stopping node and the algorithm correctly returns false. We also maintain a visited matrix to avoid revisiting stopping nodes and to ensure termination.

Approach

  1. Initialize a visited matrix to track visited positions.
  2. Start DFS from the start position.
  3. For each direction, roll the ball until it hits a wall.
  4. If the stopping position has not been visited, recursively call DFS from there.
  5. If the destination is reached, return true.
  6. If all paths are explored and the destination is not reached, return false.

Pseudocode

1
2
3
4
5
6
7
8
visited = m x n false
dfs(start):
  mark start visited
  for each direction d in 4 directions:
    next = roll_from(start, d)
    if next == dest: return true
    if not visited[next]: if dfs(next): return true
  return false

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
#include <vector>
using std::vector;

class Solution {
public:
    bool hasPath(vector<vector<int>>& maze, vector<int>& start, vector<int>& destination) {
        int m = maze.size();
        int n = maze[0].size();
        vector<vector<bool>> visited(m, vector<bool>(n, false));
        return Dfs(maze, start[0], start[1], destination, visited);
    }

private:
    bool Dfs(vector<vector<int>>& maze, int row, int col, vector<int>& dest,
             vector<vector<bool>>& visited) {
        if (visited[row][col]) return false;
        if (row == dest[0] && col == dest[1]) return true;

        visited[row][col] = true;
        int dirs[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
        int m = maze.size();
        int n = maze[0].size();

        for (auto& d : dirs) {
            int r = row;
            int c = col;
            // Roll until the next cell would be a wall; (r, c) becomes the stopping cell.
            while (r + d[0] >= 0 && r + d[0] < m && c + d[1] >= 0 && c + d[1] < n &&
                   maze[r + d[0]][c + d[1]] == 0) {
                r += d[0];
                c += d[1];
            }
            if (Dfs(maze, r, c, dest, visited)) return true;
        }
        return false;
    }
};
 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
class Solution {
  public boolean hasPath(int[][] maze, int[] start, int[] destination) {
    int m = maze.length;
    int n = maze[0].length;
    boolean[][] visited = new boolean[m][n];
    return dfs(maze, start[0], start[1], destination, visited);
  }

  private boolean dfs(int[][] maze, int row, int col, int[] dest, boolean[][] visited) {
    if (visited[row][col]) {
      return false;
    }
    if (row == dest[0] && col == dest[1]) {
      return true;
    }

    visited[row][col] = true;
    int[][] dirs = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};

    for (int[] d : dirs) {
      int r = row;
      int c = col;
      // Roll until the next cell would be a wall; (r, c) becomes the stopping cell.
      while (r + d[0] >= 0 && r + d[0] < maze.length
          && c + d[1] >= 0 && c + d[1] < maze[0].length
          && maze[r + d[0]][c + d[1]] == 0) {
        r += d[0];
        c += d[1];
      }
      if (dfs(maze, r, c, dest, visited)) {
        return true;
      }
    }
    return false;
  }
}
 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
class Solution:
  def hasPath(self, maze: List[List[int]], start: List[int], destination: List[int]) -> bool:
    """Return True if the ball can stop at the destination.

    Args:
      maze: 2-D grid where 0 is empty and 1 is a wall.
      start: [row, col] start coordinate.
      destination: [row, col] destination coordinate.

    Returns:
      True if exists a sequence of rolls that stops exactly at destination.
    """

    rows, cols = len(maze), len(maze[0])
    visited = [[False] * cols for _ in range(rows)]

    def rollUntilStop(r: int, c: int, dr: int, dc: int) -> tuple[int, int]:
      while 0 <= r + dr < rows and 0 <= c + dc < cols and maze[r + dr][c + dc] == 0:
        r += dr
        c += dc
      return r, c

    def dfs(r: int, c: int) -> bool:
      if visited[r][c]:
        return False
      if [r, c] == destination:
        return True
      visited[r][c] = True
      for dr, dc in ((0, 1), (1, 0), (0, -1), (-1, 0)):
        nr, nc = rollUntilStop(r, c, dr, dc)
        if not visited[nr][nc] and dfs(nr, nc):
          return True
      return False

    return dfs(start[0], start[1])

Complexity

  • ⏰ Time complexity: O(mn), where m and n are the maze dimensions; each cell is visited at most once.
  • 🧺 Space complexity: O(mn), for the visited matrix and recursion stack.

Method 2 - BFS (roll-to-stop transitions)

Intuition

Use the same rolling-to-stop transitions but perform BFS instead of DFS. For the simple reachability here BFS and DFS both work; BFS is required for The Maze 2 - Shortest Distance (shortest distance) where we must track distances.

Approach

  1. Use a queue of stopping positions (cells where the ball comes to rest).
  2. Start with the given start position and enqueue it (boolean reachability) or initialize distances (shortest-distance variants).
  3. For each popped stop, roll in the 4 directions until the ball hits a wall and obtain the next stopping cell. If not visited, mark and enqueue.
  4. For boolean reachability (this problem) stop early when destination is reached; for shortest-distance variants keep distance bookkeeping (see next subsection).

This is effectively a graph search over stopping cells rather than every intermediate cell while rolling.

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
#include <vector>
#include <queue>
using std::vector;
using std::queue;

class Solution {
public:
  bool hasPath(vector<vector<int>>& maze, vector<int>& start, vector<int>& destination) {
    int m = maze.size();
    int n = maze[0].size();
    vector<vector<bool>> visited(m, vector<bool>(n, false));
    int dirs[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};

    queue<std::pair<int, int>> q;
    q.emplace(start[0], start[1]);
    visited[start[0]][start[1]] = true;

    while (!q.empty()) {
      auto cur = q.front();
      q.pop();
      int r = cur.first;
      int c = cur.second;
      if (r == destination[0] && c == destination[1]) return true;
      for (auto& d : dirs) {
        int nr = r;
        int nc = c;
        // Roll until the next cell would be a wall; (nr, nc) becomes the stopping cell.
        while (nr + d[0] >= 0 && nr + d[0] < m && nc + d[1] >= 0 && nc + d[1] < n &&
             maze[nr + d[0]][nc + d[1]] == 0) {
          nr += d[0];
          nc += d[1];
        }
        if (!visited[nr][nc]) {
          visited[nr][nc] = true;
          q.emplace(nr, nc);
        }
      }
    }
    return false;
  }
};
 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
class Solution {
  public boolean hasPath(int[][] maze, int[] start, int[] destination) {
    int m = maze.length;
    int n = maze[0].length;
    boolean[][] visited = new boolean[m][n];
    int[][] dirs = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};

    Queue<int[]> q = new LinkedList<>();
    q.offer(start);
    visited[start[0]][start[1]] = true;

    while (!q.isEmpty()) {
      int[] cur = q.poll();
      if (cur[0] == destination[0] && cur[1] == destination[1]) {
        return true;
      }
      for (int[] d : dirs) {
        int r = cur[0];
        int c = cur[1];
        // Roll until hitting a wall; (r,c) will be the stopping cell.
        while (r + d[0] >= 0 && r + d[0] < m
            && c + d[1] >= 0 && c + d[1] < n
            && maze[r + d[0]][c + d[1]] == 0) {
          r += d[0];
          c += d[1];
        }
        if (!visited[r][c]) {
          visited[r][c] = true;
          q.offer(new int[]{r, c});
        }
      }
    }
    return false;
  }
}
 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 hasPath(self, maze: List[List[int]], start: List[int], destination: List[int]) -> bool:
    """Return True if the ball can stop at the destination using BFS over stopping cells."""

    rows, cols = len(maze), len(maze[0])
    visited = [[False] * cols for _ in range(rows)]
    q = deque([(start[0], start[1])])
    visited[start[0]][start[1]] = True
    dirs = ((0, 1), (1, 0), (0, -1), (-1, 0))

    while q:
      r, c = q.popleft()
      if [r, c] == destination:
        return True
      for dr, dc in dirs:
        nr, nc = r, c
        while 0 <= nr + dr < rows and 0 <= nc + dc < cols and maze[nr + dr][nc + dc] == 0:
          nr += dr
          nc += dc
        if not visited[nr][nc]:
          visited[nr][nc] = True
          q.append((nr, nc))
    return False

Complexity

  • ⏰ Time complexity: O(m * n) — each stopping cell is enqueued at most once; rolling across straight segments amortizes to O(mn) total.
  • 🧺 Space complexity: O(m * n) — visited matrix plus queue.