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 nmaze, 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).
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: trueExplanation: One possible way is: left -> down -> left -> down -> right -> down -> right.
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: falseExplanation: 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.
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.
visited = m x n false
dfs(start):
mark start visited
for each direction d in4 directions:
next = roll_from(start, d)
if next == dest: return true
ifnot visited[next]: if dfs(next): return true
return false
#include<vector>using std::vector;
classSolution {
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));
returnDfs(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;
}
};
classSolution {
publicbooleanhasPath(int[][] maze, int[] start, int[] destination) {
int m = maze.length;
int n = maze[0].length;
boolean[][] visited =newboolean[m][n];
return dfs(maze, start[0], start[1], destination, visited);
}
privatebooleandfs(int[][] maze, int row, int col, int[] dest, boolean[][] visited) {
if (visited[row][col]) {
returnfalse;
}
if (row == dest[0]&& col == dest[1]) {
returntrue;
}
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)) {
returntrue;
}
}
returnfalse;
}
}
classSolution:
defhasPath(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)]
defrollUntilStop(r: int, c: int, dr: int, dc: int) -> tuple[int, int]:
while0<= r + dr < rows and0<= c + dc < cols and maze[r + dr][c + dc] ==0:
r += dr
c += dc
return r, c
defdfs(r: int, c: int) -> bool:
if visited[r][c]:
returnFalseif [r, c] == destination:
returnTrue visited[r][c] =Truefor dr, dc in ((0, 1), (1, 0), (0, -1), (-1, 0)):
nr, nc = rollUntilStop(r, c, dr, dc)
ifnot visited[nr][nc] and dfs(nr, nc):
returnTruereturnFalsereturn dfs(start[0], start[1])
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.
Use a queue of stopping positions (cells where the ball comes to rest).
Start with the given start position and enqueue it (boolean reachability) or initialize distances (shortest-distance variants).
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.
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.
#include<vector>#include<queue>using std::vector;
using std::queue;
classSolution {
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;
}
};
classSolution {
publicbooleanhasPath(int[][] maze, int[] start, int[] destination) {
int m = maze.length;
int n = maze[0].length;
boolean[][] visited =newboolean[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]) {
returntrue;
}
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(newint[]{r, c});
}
}
}
returnfalse;
}
}
classSolution:
defhasPath(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:
returnTruefor dr, dc in dirs:
nr, nc = r, c
while0<= nr + dr < rows and0<= nc + dc < cols and maze[nr + dr][nc + dc] ==0:
nr += dr
nc += dc
ifnot visited[nr][nc]:
visited[nr][nc] =True q.append((nr, nc))
returnFalse