Shortest Clear Route Through a Blocked Board
Solve this ProblemYou are given a square-or-rectangular board where 0 is an open cell and 1 is a blocked cell. Find the shortest route from the top-left cell to the bottom-right cell that only visits open cells, where each move goes to any of the 8 surrounding cells. Return the number of cells on that route (both ends counted), or -1 when no route exists.
Because every move costs the same, a breadth-first search over the cells finds the answer in one pass.
Test Case 1:
Test Case 2:
Test Case 3:
Constraints
- ◆
1 ≤ rows, cols ≤ 12; grid[r][c] is 0 (open) or 1 (blocked) - ◆
A route starts at the top-left cell and ends at the bottom-right cell, visiting only open cells - ◆
You may step to any of the 8 surrounding cells (sides and corners) - ◆
Return the number of cells on the shortest route (including both ends), or -1 if there is none
Try the Dry Run
Don't just read the solution — watch it execute, one step at a time.
Approach & Solutions
Brute Force — Keep Relaxing Distances Until Nothing Improves
BruteKeep a distance table where the start has distance 1 and every other cell is unknown (infinite). Sweep over the whole grid again and again: whenever a cell has a known distance, offer that distance plus one to each open cell around it, and keep it if it is better than what the neighbour has. Stop when a full sweep changes nothing. Distances settle only after several sweeps (up to one per cell on the route), so this costs O((R·C)²).
O((R·C)²)O(R·C)1class Solution {
2 public int shortestClearPath(int[][] grid) {
3 int rows = grid.length, cols = grid[0].length;
4 if (grid[0][0] == 1 || grid[rows - 1][cols - 1] == 1) return -1;
5 int INF = Integer.MAX_VALUE;
6 int[][] dist = new int[rows][cols];
7 for (int[] row : dist) Arrays.fill(row, INF);
8 dist[0][0] = 1;
9 boolean changed = true;
10 while (changed) {
11 changed = false;
12 for (int r = 0; r < rows; r++) {
13 for (int c = 0; c < cols; c++) {
14 if (dist[r][c] == INF) continue;
15 for (int dr = -1; dr <= 1; dr++) {
16 for (int dc = -1; dc <= 1; dc++) {
17 int nr = r + dr, nc = c + dc;
18 if (nr >= 0 && nr < rows && nc >= 0 && nc < cols && grid[nr][nc] == 0 && dist[r][c] + 1 < dist[nr][nc]) {
19 dist[nr][nc] = dist[r][c] + 1;
20 changed = true;
21 }
22 }
23 }
24 }
25 }
26 }
27 return dist[rows - 1][cols - 1] == INF ? -1 : dist[rows - 1][cols - 1];
28 }
29}Optimal — Breadth-First Search With Eight Directions
OptimalEvery step costs the same, so a breadth-first search finds the shortest route: the first time the search reaches the bottom-right cell is via a shortest route. Start from the top-left cell with distance 1. Take a cell from the queue, and for each of its 8 surrounding cells that is open and has not been reached, record distance + 1 and enqueue it. Each cell is enqueued once: O(R·C). If the queue empties first, there is no route.
O(R·C)O(R·C)1class Solution {
2 public int shortestClearPath(int[][] grid) {
3 int rows = grid.length, cols = grid[0].length;
4 if (grid[0][0] == 1 || grid[rows - 1][cols - 1] == 1) return -1;
5 int[][] dist = new int[rows][cols];
6 dist[0][0] = 1;
7 Deque<int[]> queue = new ArrayDeque<>();
8 queue.add(new int[]{0, 0});
9 while (!queue.isEmpty()) {
10 int[] cell = queue.poll();
11 int r = cell[0], c = cell[1];
12 if (r == rows - 1 && c == cols - 1) return dist[r][c];
13 for (int dr = -1; dr <= 1; dr++) {
14 for (int dc = -1; dc <= 1; dc++) {
15 int nr = r + dr, nc = c + dc;
16 if (nr >= 0 && nr < rows && nc >= 0 && nc < cols && grid[nr][nc] == 0 && dist[nr][nc] == 0) {
17 dist[nr][nc] = dist[r][c] + 1;
18 queue.add(new int[]{nr, nc});
19 }
20 }
21 }
22 }
23 return -1;
24 }
25}