The Maze
Medium · Graphs · Explanation and code example
Breadth First Search
How it works
BFS offers an alternative traversal strategy that explores all stopping positions at each "distance level" before moving deeper. While DFS might go deep into one path before backtracking, BFS systematically explores positions in order of how many rolls it takes to reach them.
The core rolling mechanic remains the same: the ball rolls until hitting a wall, and we only consider positions where the ball actually stops.
Steps
- Initialize a visited matrix and a queue with the starting position.
- Mark the starting position as visited.
- While the queue is not empty:
- Dequeue the current position.
- If it equals the destination, return
true. - For each of the four directions:
- Roll the ball until it hits a wall or boundary.
- Step back to find the stopping position.
- If not visited, mark it visited and add to the queue.
- If the queue empties without finding the destination, return
false.
Complexity
- Time complexity:
O(m × n × (m + n)) - Space complexity:
O(m × n)
Where
mandnare the number of rows and columns inmaze.
Things to watch for
Treating This as a Standard Grid Traversal
In typical grid problems, movement is one cell at a time in any direction. Here, the ball rolls continuously until hitting a wall. A common mistake is moving only one cell per step or checking neighbors adjacently. The ball can only stop at positions next to walls, not at arbitrary empty cells.
Checking Destination During Rolling Instead of After Stopping
The ball can only stop when it hits a wall, not mid-roll. Even if the destination is on the rolling path, the ball cannot stop there unless a wall forces it to. Check if the current position equals the destination only after the ball has stopped rolling.
Forgetting to Step Back After the Rolling Loop
The while loop condition checks the next cell before moving, but after exiting, the ball is one step past a valid position (inside a wall or out of bounds). Always subtract the direction vector after the loop to get the actual stopping cell.
Python code example
from typing import List
from collections import deque
class Solution:
def hasPath(self, maze: List[List[int]], start: List[int], destination: List[int]) -> bool:
m = len(maze)
n = len(maze[0])
visit = [[False] * n for _ in range(m)]
queue = deque()
queue.append(start)
visit[start[0]][start[1]] = True
dirX = [0, 1, 0, -1]
dirY = [-1, 0, 1, 0]
while queue:
curr = queue.popleft()
if curr[0] == destination[0] and curr[1] == destination[1]:
return True
for i in range(4):
r = curr[0]
c = curr[1]
# Move the ball in the chosen direction until it can.
while r >= 0 and r < m and c >= 0 and c < n and maze[r][c] == 0:
r += dirX[i]
c += dirY[i]
# Revert the last move to get the cell to which the ball rolls.
r -= dirX[i]
c -= dirY[i]
if not visit[r][c]:
queue.append([r, c])
visit[r][c] = True
return False
C++ code example
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>> visit(m, vector<bool>(n, false));
vector<int> dirX{0, 1, 0, -1};
vector<int> dirY{-1, 0, 1, 0};
queue<vector<int>> q;
q.push(start);
visit[start[0]][start[1]] = true;
while (!q.empty()) {
vector<int> curr = q.front();
q.pop();
if (curr[0] == destination[0] && curr[1] == destination[1]) {
return true;
}
for (int i = 0; i < 4; i++) {
int r = curr[0];
int c = curr[1];
// Move the ball in the chosen direction until it can.
while (r >= 0 && r < m && c >= 0 && c < n && maze[r][c] == 0) {
r += dirX[i];
c += dirY[i];
}
// Revert the last move to get the cell to which the ball rolls.
r -= dirX[i];
c -= dirY[i];
if (!visit[r][c]) {
q.push({r, c});
visit[r][c] = true;
}
}
}
return false;
}
};
Source and license
Adapted from NeetCode’s source · MIT license. Node types are supplied by LeetCode where needed.