The Maze
Problem
A ball rolls in a 4-direction maze; once moving it does not stop until it hits a wall. Given start and destination, decide whether the ball can stop at destination.
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], dest=[4,4]truefrom collections import deque
def has_path(maze, start, dest):
R, C = len(maze), len(maze[0])
DIRS = [(-1,0),(1,0),(0,-1),(0,1)]
seen = {tuple(start)}
q = deque([tuple(start)])
while q:
x, y = q.popleft()
if [x, y] == dest: return True
for dx, dy in DIRS:
nx, ny = x, y
while 0 <= nx+dx < R and 0 <= ny+dy < C and maze[nx+dx][ny+dy] == 0:
nx += dx; ny += dy
if (nx, ny) not in seen:
seen.add((nx, ny)); q.append((nx, ny))
return Falsefunction hasPath(maze, start, dest) {
const R = maze.length, C = maze[0].length;
const DIRS = [[-1,0],[1,0],[0,-1],[0,1]];
const seen = new Set([start.join(",")]);
const q = [start];
while (q.length) {
const [x, y] = q.shift();
if (x === dest[0] && y === dest[1]) return true;
for (const [dx, dy] of DIRS) {
let nx = x, ny = y;
while (nx + dx >= 0 && nx + dx < R && ny + dy >= 0 && ny + dy < C && maze[nx+dx][ny+dy] === 0) { nx += dx; ny += dy; }
const k = nx + "," + ny;
if (!seen.has(k)) { seen.add(k); q.push([nx, ny]); }
}
}
return false;
}class Solution {
public boolean hasPath(int[][] m, int[] start, int[] dest) {
int R = m.length, C = m[0].length;
int[][] DIRS = {{-1,0},{1,0},{0,-1},{0,1}};
boolean[][] seen = new boolean[R][C];
Queue q = new ArrayDeque<>();
q.add(start); seen[start[0]][start[1]] = true;
while (!q.isEmpty()) {
int[] p = q.poll();
if (p[0] == dest[0] && p[1] == dest[1]) return true;
for (int[] d : DIRS) {
int x = p[0], y = p[1];
while (x + d[0] >= 0 && x + d[0] < R && y + d[1] >= 0 && y + d[1] < C && m[x+d[0]][y+d[1]] == 0) { x += d[0]; y += d[1]; }
if (!seen[x][y]) { seen[x][y] = true; q.add(new int[]{x, y}); }
}
}
return false;
}
} bool hasPath(vector>& m, vector& start, vector& dest) {
int R = m.size(), C = m[0].size();
vector> DIRS = {{-1,0},{1,0},{0,-1},{0,1}};
vector> seen(R, vector(C, false));
queue> q;
q.push({start[0], start[1]}); seen[start[0]][start[1]] = true;
while (!q.empty()) {
auto [x, y] = q.front(); q.pop();
if (x == dest[0] && y == dest[1]) return true;
for (auto& d : DIRS) {
int nx = x, ny = y;
while (nx + d[0] >= 0 && nx + d[0] < R && ny + d[1] >= 0 && ny + d[1] < C && m[nx+d[0]][ny+d[1]] == 0) { nx += d[0]; ny += d[1]; }
if (!seen[nx][ny]) { seen[nx][ny] = true; q.push({nx, ny}); }
}
}
return false;
} Explanation
The catch in this maze is that the ball keeps rolling until a wall stops it — it can't stop in the middle of a corridor. So the natural graph nodes are the stopping positions, and from each stop the ball can move to a handful of other stops. We just need to know if the destination is one of those reachable stops, which is a plain reachability question, perfect for BFS.
Starting from the start cell, we explore stop by stop. For each of the four directions, the inner while loop slides the ball as far as it can go before a wall, giving the next stopping cell.
A seen set records stops we've already queued so we never process the same stop twice. Each newly discovered stop is added to the queue to be explored later.
If we ever pop the destination cell off the queue, we return true. If the queue empties without reaching it, the ball cannot stop there, so we return false.
Example: from start = [0,4], sliding down and across through the open corridors eventually produces a stop at dest = [4,4], so the answer is true.