The Maze II
Problem
A ball rolls until a wall. Return the shortest distance (number of empty cells passed) from start to destination, or −1.
maze=…, start=[0,4], dest=[4,4]12import heapq
def shortest_distance(maze, start, dest):
R, C = len(maze), len(maze[0])
DIRS = [(-1,0),(1,0),(0,-1),(0,1)]
dist = {(start[0], start[1]): 0}
pq = [(0, start[0], start[1])]
while pq:
d, x, y = heapq.heappop(pq)
if [x, y] == dest: return d
if d > dist[(x, y)]: continue
for dx, dy in DIRS:
nx, ny, nd = x, y, 0
while 0 <= nx+dx < R and 0 <= ny+dy < C and maze[nx+dx][ny+dy] == 0:
nx += dx; ny += dy; nd += 1
nd2 = d + nd
if nd2 < dist.get((nx, ny), float("inf")):
dist[(nx, ny)] = nd2
heapq.heappush(pq, (nd2, nx, ny))
return -1function shortestDistance(maze, start, dest) {
const R = maze.length, C = maze[0].length;
const DIRS = [[-1,0],[1,0],[0,-1],[0,1]];
const dist = new Map(); dist.set(start.join(","), 0);
const pq = [[0, start[0], start[1]]];
while (pq.length) {
pq.sort((a, b) => a[0] - b[0]);
const [d, x, y] = pq.shift();
if (x === dest[0] && y === dest[1]) return d;
if (d > dist.get(x + "," + y)) continue;
for (const [dx, dy] of DIRS) {
let nx = x, ny = y, nd = 0;
while (nx + dx >= 0 && nx + dx < R && ny + dy >= 0 && ny + dy < C && maze[nx+dx][ny+dy] === 0) { nx += dx; ny += dy; nd++; }
const nd2 = d + nd, k = nx + "," + ny;
if (nd2 < (dist.get(k) ?? Infinity)) { dist.set(k, nd2); pq.push([nd2, nx, ny]); }
}
}
return -1;
}class Solution {
public int shortestDistance(int[][] m, int[] start, int[] dest) {
int R = m.length, C = m[0].length;
int[][] DIRS = {{-1,0},{1,0},{0,-1},{0,1}};
int[][] dist = new int[R][C];
for (int[] row : dist) Arrays.fill(row, Integer.MAX_VALUE);
dist[start[0]][start[1]] = 0;
PriorityQueue pq = new PriorityQueue<>((a, b) -> a[0] - b[0]);
pq.offer(new int[]{0, start[0], start[1]});
while (!pq.isEmpty()) {
int[] cur = pq.poll();
int d = cur[0], x = cur[1], y = cur[2];
if (x == dest[0] && y == dest[1]) return d;
if (d > dist[x][y]) continue;
for (int[] dir : DIRS) {
int nx = x, ny = y, nd = 0;
while (nx + dir[0] >= 0 && nx + dir[0] < R && ny + dir[1] >= 0 && ny + dir[1] < C && m[nx+dir[0]][ny+dir[1]] == 0) { nx += dir[0]; ny += dir[1]; nd++; }
if (d + nd < dist[nx][ny]) { dist[nx][ny] = d + nd; pq.offer(new int[]{d + nd, nx, ny}); }
}
}
return -1;
}
} int shortestDistance(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> dist(R, vector(C, INT_MAX));
dist[start[0]][start[1]] = 0;
priority_queue, vector>, greater<>> pq;
pq.push({0, start[0], start[1]});
while (!pq.empty()) {
auto [d, x, y] = pq.top(); pq.pop();
if (x == dest[0] && y == dest[1]) return d;
if (d > dist[x][y]) continue;
for (auto& dir : DIRS) {
int nx = x, ny = y, nd = 0;
while (nx + dir[0] >= 0 && nx + dir[0] < R && ny + dir[1] >= 0 && ny + dir[1] < C && m[nx+dir[0]][ny+dir[1]] == 0) { nx += dir[0]; ny += dir[1]; nd++; }
if (d + nd < dist[nx][ny]) { dist[nx][ny] = d + nd; pq.push({d + nd, nx, ny}); }
}
}
return -1;
} Explanation
A ball doesn't move one cell at a time — it rolls until it hits a wall. So the natural graph here has nodes at the stopping points, and the cost of each edge is how many cells the ball slides before stopping. Since edges have different weights, we use Dijkstra's algorithm to find the shortest total distance.
Dijkstra always expands the closest unfinished cell first, using a min-heap (pq) keyed by distance. The dist map records the best distance found so far to each stopping cell.
For each of the four directions, the inner while loop rolls the ball as far as it can, counting nd cells. If reaching that stop with total distance d + nd beats the recorded value, we update dist and push the new stop onto the heap.
When we pop the destination, its distance is guaranteed minimal, so we return it. The check if d > dist[(x,y)]: continue skips stale heap entries. If the heap empties without reaching the goal, the answer is -1.
Example: rolling from start = [0,4], each slide adds its length to the running distance, and Dijkstra picks the cheapest combination of rolls, reaching dest = [4,4] in 12 cells.