DSA-101 · Eight-neighbor BFS with path length measured in cells
Shortest Path in a Binary Matrix
Core · Java 21 · Version 1 · editorial draft
Java reference and baseline verified on JDK 21: 5083 deterministic checks. Learner drafts are not executed.
Understand the problem
Return the fewest cells in an open path from the top-left to bottom-right of a square binary grid using eight-direction moves. Return -1 when no such path exists.
- grid is nonnull, square n×n with at most 100,000 cells and nonnull rows; size bound is a precondition. Cells are exactly 0=open or 1=blocked. Null outer input throws NullPointerException; nonsquare/null rows and invalid cell codes throw IllegalArgumentException before endpoint shortcuts.
- Preserve all source cell values and row references; shared input row objects are allowed because coordinates, not row objects, identify vertices. Empty square input returns -1. A blocked start or destination returns -1; a single open cell returns 1.
- All eight neighboring directions are legal, including diagonals even if adjacent orthogonal cells are blocked. Count cells, not edges: start contributes one. Return only length; no particular route or complete all-cell distance matrix is promised.
Examples
Input:
[[0,1,0],[0,0,0],[1,1,0]]
Output:3The diagonal route (0,0)→(1,1)→(2,2) contains three cells.
Input:
[[0,1],[1,0]]
Output:2The diagonal is permitted despite the blocked orthogonal neighbors.
Input:
[[0]]
Output:1The path contains its one open endpoint cell.
Before you start
- Unweighted shortest-path BFS and first-discovery distances
- Eight-neighbor adjacency and edge-versus-cell units
Recognize the structure
Each open coordinate is a vertex with up to eight unit-cost neighbors. FIFO order makes the first discovered distance shortest; a separate distance matrix preserves the binary input and distinguishes undiscovered state.
Try before revealing
Hint 1
Model open cells as a unit-weight graph.
Hint 2
There are eight possible moves, and start distance is one cell.
Hint 3
BFS with a separate discovery-distance matrix; stop at the first target pop.
Derive the solution
Reveal the baseline, optimized reasoning, and Java code
Synchronous full-grid shortest-distance relaxation
Initialize the open start to one and every other distance to infinity. In each round, use a snapshot of prior distances to relax each open cell from its eight neighbors; repeat until no value improves. After k rounds, paths using at most k edges have propagated. This is correct but can scan every cell for many rounds, unlike a frontier-driven BFS.
Improve the baseline
Validate the entire square before early returns
Check all rows and cell codes first. Then reject empty input or blocked endpoints without allocating traversal state.
Seed distance one and claim on discovery
Set start distance to one. For each popped cell, each in-bounds open neighbor with distance zero gets parent+1 before enqueueing.
Return when the destination is popped
The queue processes nondecreasing established distances. The first target pop is sufficient; other queued cells may remain unexplored and need not receive final processing.
Why it is correct
Distance invariant
Each discovered coordinate has an open route with its stored cell count. Initialization is the one-cell start route, and each edge extension adds one new cell.
Shortest first discovery
Any shorter path to a newly discovered cell would have a predecessor at a smaller BFS layer, which would already have claimed it. Thus discovery distances are minimum.
Correct early success or failure
The first dequeued destination has the minimum path length. If the queue exhausts first, every open coordinate reachable under the eight-neighbor rule has been explored and no valid destination route exists.
Complete Java reference and baseline
Save as Solution.java. Node definitions and imports are included where needed. The baseline is included for comparison; respect its input-size limits.
import java.util.*;
public final class Solution {
private static int validate(int[][] grid) {
Objects.requireNonNull(grid,"grid");int n=grid.length;
for(int[] row:grid){if(row==null||row.length!=n)throw new IllegalArgumentException("expected square");for(int value:row)if(value!=0&&value!=1)throw new IllegalArgumentException("invalid cell");}return n;
}
public static int shortestPath(int[][] grid) {
int n=validate(grid);if(n==0||grid[0][0]!=0||grid[n-1][n-1]!=0)return -1;
int[][] distance=new int[n][n];ArrayDeque<int[]> queue=new ArrayDeque<>();distance[0][0]=1;queue.addLast(new int[]{0,0});
while(!queue.isEmpty()) {
int[] cell=queue.removeFirst();
if(cell[0]==n-1&&cell[1]==n-1)return distance[cell[0]][cell[1]];
for(int dr=-1;dr<=1;dr++)for(int dc=-1;dc<=1;dc++) {
if(dr==0&&dc==0)continue;int nr=cell[0]+dr,nc=cell[1]+dc;
if(nr<0||nr>=n||nc<0||nc>=n||grid[nr][nc]!=0||distance[nr][nc]!=0)continue;
distance[nr][nc]=distance[cell[0]][cell[1]]+1;queue.addLast(new int[]{nr,nc});
}
}
return -1;
}
public static int baseline(int[][] grid) {
int n=validate(grid);if(n==0||grid[0][0]!=0||grid[n-1][n-1]!=0)return -1;
int[][] distance=new int[n][n];for(int[] row:distance)Arrays.fill(row,Integer.MAX_VALUE);distance[0][0]=1;
boolean changed;
do{changed=false;int[][] next=new int[n][];for(int r=0;r<n;r++)next[r]=distance[r].clone();for(int r=0;r<n;r++)for(int c=0;c<n;c++)if(grid[r][c]==0)for(int dr=-1;dr<=1;dr++)for(int dc=-1;dc<=1;dc++){if(dr==0&&dc==0)continue;int nr=r+dr,nc=c+dc;if(nr>=0&&nr<n&&nc>=0&&nc<n&&distance[nr][nc]!=Integer.MAX_VALUE&&distance[nr][nc]+1<next[r][c]){next[r][c]=distance[nr][nc]+1;changed=true;}}distance=next;}while(changed);
return distance[n-1][n-1]==Integer.MAX_VALUE?-1:distance[n-1][n-1];
}
}
Read the meaningful blocks
Zero belongs to two different representations
Source zero means open; distance-matrix zero means undiscovered. They are different arrays and concepts.
Do not add corner-cut restrictions
This API allows a diagonal between two open diagonal cells even when their orthogonal neighbors are blocked.
Do not claim complete distances after early return
Pending cells and undiscovered regions may remain; only the returned target distance is required.
Complexity
For B=n² cells, main worst-case time and auxiliary distance/queue storage are O(B+1). Full validation costs O(B) even if endpoints are blocked; that early-return path uses constant additional traversal space.
The synchronous baseline can take O(B²+1) time and O(B+1) snapshot distance storage. Finite shortest routes never need more than B cells, so int distances are safe under the declared bound.
Exact-state walkthroughs
Reveal normal and boundary traces
Eight-direction shortest route counts cells
Input: [[0,1,0],[0,0,0],[1,1,0]] · Minimum cell count / −1: 3
Step 1 of 13: Seed the open start with a one-cell path.
Distance zero means undiscovered in this separate matrix. Returned length counts cells, including start and destination.
Phase: seed.
Unchanged source grid
Coordinate queue — front at left; already claimed
- (0, 0)
Separate distances — 0 undiscovered; positive counts cells
Source 0 means open and 1 means blocked. Distances use a separate meaning: 0 undiscovered, 1 the starting cell. All eight directions are legal, including corner diagonals. At a target return, queued alternatives may remain and unvisited cells are not a complete distance map.
The exact state table and static walkthrough below provide the same information without relying on color.
| Variable | Value |
|---|---|
| source | [[0,1,0],[0,0,0],[1,1,0]] |
| grid | [[0,1,0],[0,0,0],[1,1,0]] |
| queue | [[0,0]] |
| distance | [[1,0,0],[0,0,0],[0,0,0]] |
| phase | "seed" |
| current | null |
See the affected Java block
1 import java.util.*; 2 public final class Solution { 3 private static int validate(int[][] grid) { 4 Objects.requireNonNull(grid,"grid");int n=grid.length; 5 for(int[] row:grid){if(row==null||row.length!=n)throw new IllegalArgumentException("expected square");for(int value:row)if(value!=0&&value!=1)throw new IllegalArgumentException("invalid cell");}return n; 6 } 7 public static int shortestPath(int[][] grid) { 8 int n=validate(grid);if(n==0||grid[0][0]!=0||grid[n-1][n-1]!=0)return -1; 9 int[][] distance=new int[n][n];ArrayDeque<int[]> queue=new ArrayDeque<>();distance[0][0]=1;queue.addLast(new int[]{0,0}); 10 while(!queue.isEmpty()) { 11 int[] cell=queue.removeFirst(); 12 if(cell[0]==n-1&&cell[1]==n-1)return distance[cell[0]][cell[1]]; 13 for(int dr=-1;dr<=1;dr++)for(int dc=-1;dc<=1;dc++) { 14 if(dr==0&&dc==0)continue;int nr=cell[0]+dr,nc=cell[1]+dc; 15 if(nr<0||nr>=n||nc<0||nc>=n||grid[nr][nc]!=0||distance[nr][nc]!=0)continue; 16 distance[nr][nc]=distance[cell[0]][cell[1]]+1;queue.addLast(new int[]{nr,nc}); 17 } 18 } 19 return -1; 20 } 21 public static int baseline(int[][] grid) { 22 int n=validate(grid);if(n==0||grid[0][0]!=0||grid[n-1][n-1]!=0)return -1; 23 int[][] distance=new int[n][n];for(int[] row:distance)Arrays.fill(row,Integer.MAX_VALUE);distance[0][0]=1; 24 boolean changed; 25 do{changed=false;int[][] next=new int[n][];for(int r=0;r<n;r++)next[r]=distance[r].clone();for(int r=0;r<n;r++)for(int c=0;c<n;c++)if(grid[r][c]==0)for(int dr=-1;dr<=1;dr++)for(int dc=-1;dc<=1;dc++){if(dr==0&&dc==0)continue;int nr=r+dr,nc=c+dc;if(nr>=0&&nr<n&&nc>=0&&nc<n&&distance[nr][nc]!=Integer.MAX_VALUE&&distance[nr][nc]+1<next[r][c]){next[r][c]=distance[nr][nc]+1;changed=true;}}distance=next;}while(changed); 26 return distance[n-1][n-1]==Integer.MAX_VALUE?-1:distance[n-1][n-1]; 27 } 28 } 29
Highlight locates the relevant statement or block; one trace step may summarize several assignments.
Read the full static trace
- Seed the open start with a one-cell path.
Distance zero means undiscovered in this separate matrix. Returned length counts cells, including start and destination.
- source
[[0,1,0],[0,0,0],[1,1,0]]- grid
[[0,1,0],[0,0,0],[1,1,0]]- queue
[[0,0]]- distance
[[1,0,0],[0,0,0],[0,0,0]]- phase
"seed"- current
null
- Expand one discovered open cell using eight directions.
Diagonals are legal even when the two adjacent orthogonal cells are blocked.
- source
[[0,1,0],[0,0,0],[1,1,0]]- grid
[[0,1,0],[0,0,0],[1,1,0]]- queue
[]- distance
[[1,0,0],[0,0,0],[0,0,0]]- phase
"visit"- current
[0,0]
- Claim one open eight-neighbor with its first distance.
One discovery owner per coordinate prevents duplicate work and preserves shortest distance. The binary source grid stays unchanged.
- source
[[0,1,0],[0,0,0],[1,1,0]]- grid
[[0,1,0],[0,0,0],[1,1,0]]- queue
[[1,0]]- distance
[[1,0,0],[2,0,0],[0,0,0]]- phase
"claim"- current
[0,0]- claimed
[1,0]
- Claim one open eight-neighbor with its first distance.
One discovery owner per coordinate prevents duplicate work and preserves shortest distance. The binary source grid stays unchanged.
- source
[[0,1,0],[0,0,0],[1,1,0]]- grid
[[0,1,0],[0,0,0],[1,1,0]]- queue
[[1,0],[1,1]]- distance
[[1,0,0],[2,2,0],[0,0,0]]- phase
"claim"- current
[0,0]- claimed
[1,1]
- Expand one discovered open cell using eight directions.
Diagonals are legal even when the two adjacent orthogonal cells are blocked.
- source
[[0,1,0],[0,0,0],[1,1,0]]- grid
[[0,1,0],[0,0,0],[1,1,0]]- queue
[[1,1]]- distance
[[1,0,0],[2,2,0],[0,0,0]]- phase
"visit"- current
[1,0]
- Expand one discovered open cell using eight directions.
Diagonals are legal even when the two adjacent orthogonal cells are blocked.
- source
[[0,1,0],[0,0,0],[1,1,0]]- grid
[[0,1,0],[0,0,0],[1,1,0]]- queue
[]- distance
[[1,0,0],[2,2,0],[0,0,0]]- phase
"visit"- current
[1,1]
- Claim one open eight-neighbor with its first distance.
One discovery owner per coordinate prevents duplicate work and preserves shortest distance. The binary source grid stays unchanged.
- source
[[0,1,0],[0,0,0],[1,1,0]]- grid
[[0,1,0],[0,0,0],[1,1,0]]- queue
[[0,2]]- distance
[[1,0,3],[2,2,0],[0,0,0]]- phase
"claim"- current
[1,1]- claimed
[0,2]
- Claim one open eight-neighbor with its first distance.
One discovery owner per coordinate prevents duplicate work and preserves shortest distance. The binary source grid stays unchanged.
- source
[[0,1,0],[0,0,0],[1,1,0]]- grid
[[0,1,0],[0,0,0],[1,1,0]]- queue
[[0,2],[1,2]]- distance
[[1,0,3],[2,2,3],[0,0,0]]- phase
"claim"- current
[1,1]- claimed
[1,2]
- Claim one open eight-neighbor with its first distance.
One discovery owner per coordinate prevents duplicate work and preserves shortest distance. The binary source grid stays unchanged.
- source
[[0,1,0],[0,0,0],[1,1,0]]- grid
[[0,1,0],[0,0,0],[1,1,0]]- queue
[[0,2],[1,2],[2,2]]- distance
[[1,0,3],[2,2,3],[0,0,3]]- phase
"claim"- current
[1,1]- claimed
[2,2]
- Expand one discovered open cell using eight directions.
Diagonals are legal even when the two adjacent orthogonal cells are blocked.
- source
[[0,1,0],[0,0,0],[1,1,0]]- grid
[[0,1,0],[0,0,0],[1,1,0]]- queue
[[1,2],[2,2]]- distance
[[1,0,3],[2,2,3],[0,0,3]]- phase
"visit"- current
[0,2]
- Expand one discovered open cell using eight directions.
Diagonals are legal even when the two adjacent orthogonal cells are blocked.
- source
[[0,1,0],[0,0,0],[1,1,0]]- grid
[[0,1,0],[0,0,0],[1,1,0]]- queue
[[2,2]]- distance
[[1,0,3],[2,2,3],[0,0,3]]- phase
"visit"- current
[1,2]
- Return the first dequeued destination distance.
Pending cells may remain undispatched; FIFO already certifies the target’s minimum path length.
- source
[[0,1,0],[0,0,0],[1,1,0]]- grid
[[0,1,0],[0,0,0],[1,1,0]]- queue
[]- distance
[[1,0,3],[2,2,3],[0,0,3]]- phase
"target"- current
[2,2]
- Return the documented value, changed-grid view, fresh result, or cloned graph view.
Coordinates and object identities follow the problem-specific contract. Discovery histories are teaching views, not additional Java workspace.
- result
3
Diagonal crossing is allowed
Input: [[0,1],[1,0]] · Minimum cell count / −1: 2
Step 1 of 5: Seed the open start with a one-cell path.
Distance zero means undiscovered in this separate matrix. Returned length counts cells, including start and destination.
Phase: seed.
Unchanged source grid
Coordinate queue — front at left; already claimed
- (0, 0)
Separate distances — 0 undiscovered; positive counts cells
Source 0 means open and 1 means blocked. Distances use a separate meaning: 0 undiscovered, 1 the starting cell. All eight directions are legal, including corner diagonals. At a target return, queued alternatives may remain and unvisited cells are not a complete distance map.
The exact state table and static walkthrough below provide the same information without relying on color.
| Variable | Value |
|---|---|
| source | [[0,1],[1,0]] |
| grid | [[0,1],[1,0]] |
| queue | [[0,0]] |
| distance | [[1,0],[0,0]] |
| phase | "seed" |
| current | null |
See the affected Java block
1 import java.util.*; 2 public final class Solution { 3 private static int validate(int[][] grid) { 4 Objects.requireNonNull(grid,"grid");int n=grid.length; 5 for(int[] row:grid){if(row==null||row.length!=n)throw new IllegalArgumentException("expected square");for(int value:row)if(value!=0&&value!=1)throw new IllegalArgumentException("invalid cell");}return n; 6 } 7 public static int shortestPath(int[][] grid) { 8 int n=validate(grid);if(n==0||grid[0][0]!=0||grid[n-1][n-1]!=0)return -1; 9 int[][] distance=new int[n][n];ArrayDeque<int[]> queue=new ArrayDeque<>();distance[0][0]=1;queue.addLast(new int[]{0,0}); 10 while(!queue.isEmpty()) { 11 int[] cell=queue.removeFirst(); 12 if(cell[0]==n-1&&cell[1]==n-1)return distance[cell[0]][cell[1]]; 13 for(int dr=-1;dr<=1;dr++)for(int dc=-1;dc<=1;dc++) { 14 if(dr==0&&dc==0)continue;int nr=cell[0]+dr,nc=cell[1]+dc; 15 if(nr<0||nr>=n||nc<0||nc>=n||grid[nr][nc]!=0||distance[nr][nc]!=0)continue; 16 distance[nr][nc]=distance[cell[0]][cell[1]]+1;queue.addLast(new int[]{nr,nc}); 17 } 18 } 19 return -1; 20 } 21 public static int baseline(int[][] grid) { 22 int n=validate(grid);if(n==0||grid[0][0]!=0||grid[n-1][n-1]!=0)return -1; 23 int[][] distance=new int[n][n];for(int[] row:distance)Arrays.fill(row,Integer.MAX_VALUE);distance[0][0]=1; 24 boolean changed; 25 do{changed=false;int[][] next=new int[n][];for(int r=0;r<n;r++)next[r]=distance[r].clone();for(int r=0;r<n;r++)for(int c=0;c<n;c++)if(grid[r][c]==0)for(int dr=-1;dr<=1;dr++)for(int dc=-1;dc<=1;dc++){if(dr==0&&dc==0)continue;int nr=r+dr,nc=c+dc;if(nr>=0&&nr<n&&nc>=0&&nc<n&&distance[nr][nc]!=Integer.MAX_VALUE&&distance[nr][nc]+1<next[r][c]){next[r][c]=distance[nr][nc]+1;changed=true;}}distance=next;}while(changed); 26 return distance[n-1][n-1]==Integer.MAX_VALUE?-1:distance[n-1][n-1]; 27 } 28 } 29
Highlight locates the relevant statement or block; one trace step may summarize several assignments.
Read the full static trace
- Seed the open start with a one-cell path.
Distance zero means undiscovered in this separate matrix. Returned length counts cells, including start and destination.
- source
[[0,1],[1,0]]- grid
[[0,1],[1,0]]- queue
[[0,0]]- distance
[[1,0],[0,0]]- phase
"seed"- current
null
- Expand one discovered open cell using eight directions.
Diagonals are legal even when the two adjacent orthogonal cells are blocked.
- source
[[0,1],[1,0]]- grid
[[0,1],[1,0]]- queue
[]- distance
[[1,0],[0,0]]- phase
"visit"- current
[0,0]
- Claim one open eight-neighbor with its first distance.
One discovery owner per coordinate prevents duplicate work and preserves shortest distance. The binary source grid stays unchanged.
- source
[[0,1],[1,0]]- grid
[[0,1],[1,0]]- queue
[[1,1]]- distance
[[1,0],[0,2]]- phase
"claim"- current
[0,0]- claimed
[1,1]
- Return the first dequeued destination distance.
Pending cells may remain undispatched; FIFO already certifies the target’s minimum path length.
- source
[[0,1],[1,0]]- grid
[[0,1],[1,0]]- queue
[]- distance
[[1,0],[0,2]]- phase
"target"- current
[1,1]
- Return the documented value, changed-grid view, fresh result, or cloned graph view.
Coordinates and object identities follow the problem-specific contract. Discovery histories are teaching views, not additional Java workspace.
- result
2
Open endpoints can still be disconnected
Input: [[0,1,1],[1,1,1],[1,1,0]] · Minimum cell count / −1: -1
Step 1 of 4: Seed the open start with a one-cell path.
Distance zero means undiscovered in this separate matrix. Returned length counts cells, including start and destination.
Phase: seed.
Unchanged source grid
Coordinate queue — front at left; already claimed
- (0, 0)
Separate distances — 0 undiscovered; positive counts cells
Source 0 means open and 1 means blocked. Distances use a separate meaning: 0 undiscovered, 1 the starting cell. All eight directions are legal, including corner diagonals. At a target return, queued alternatives may remain and unvisited cells are not a complete distance map.
The exact state table and static walkthrough below provide the same information without relying on color.
| Variable | Value |
|---|---|
| source | [[0,1,1],[1,1,1],[1,1,0]] |
| grid | [[0,1,1],[1,1,1],[1,1,0]] |
| queue | [[0,0]] |
| distance | [[1,0,0],[0,0,0],[0,0,0]] |
| phase | "seed" |
| current | null |
See the affected Java block
1 import java.util.*; 2 public final class Solution { 3 private static int validate(int[][] grid) { 4 Objects.requireNonNull(grid,"grid");int n=grid.length; 5 for(int[] row:grid){if(row==null||row.length!=n)throw new IllegalArgumentException("expected square");for(int value:row)if(value!=0&&value!=1)throw new IllegalArgumentException("invalid cell");}return n; 6 } 7 public static int shortestPath(int[][] grid) { 8 int n=validate(grid);if(n==0||grid[0][0]!=0||grid[n-1][n-1]!=0)return -1; 9 int[][] distance=new int[n][n];ArrayDeque<int[]> queue=new ArrayDeque<>();distance[0][0]=1;queue.addLast(new int[]{0,0}); 10 while(!queue.isEmpty()) { 11 int[] cell=queue.removeFirst(); 12 if(cell[0]==n-1&&cell[1]==n-1)return distance[cell[0]][cell[1]]; 13 for(int dr=-1;dr<=1;dr++)for(int dc=-1;dc<=1;dc++) { 14 if(dr==0&&dc==0)continue;int nr=cell[0]+dr,nc=cell[1]+dc; 15 if(nr<0||nr>=n||nc<0||nc>=n||grid[nr][nc]!=0||distance[nr][nc]!=0)continue; 16 distance[nr][nc]=distance[cell[0]][cell[1]]+1;queue.addLast(new int[]{nr,nc}); 17 } 18 } 19 return -1; 20 } 21 public static int baseline(int[][] grid) { 22 int n=validate(grid);if(n==0||grid[0][0]!=0||grid[n-1][n-1]!=0)return -1; 23 int[][] distance=new int[n][n];for(int[] row:distance)Arrays.fill(row,Integer.MAX_VALUE);distance[0][0]=1; 24 boolean changed; 25 do{changed=false;int[][] next=new int[n][];for(int r=0;r<n;r++)next[r]=distance[r].clone();for(int r=0;r<n;r++)for(int c=0;c<n;c++)if(grid[r][c]==0)for(int dr=-1;dr<=1;dr++)for(int dc=-1;dc<=1;dc++){if(dr==0&&dc==0)continue;int nr=r+dr,nc=c+dc;if(nr>=0&&nr<n&&nc>=0&&nc<n&&distance[nr][nc]!=Integer.MAX_VALUE&&distance[nr][nc]+1<next[r][c]){next[r][c]=distance[nr][nc]+1;changed=true;}}distance=next;}while(changed); 26 return distance[n-1][n-1]==Integer.MAX_VALUE?-1:distance[n-1][n-1]; 27 } 28 } 29
Highlight locates the relevant statement or block; one trace step may summarize several assignments.
Read the full static trace
- Seed the open start with a one-cell path.
Distance zero means undiscovered in this separate matrix. Returned length counts cells, including start and destination.
- source
[[0,1,1],[1,1,1],[1,1,0]]- grid
[[0,1,1],[1,1,1],[1,1,0]]- queue
[[0,0]]- distance
[[1,0,0],[0,0,0],[0,0,0]]- phase
"seed"- current
null
- Expand one discovered open cell using eight directions.
Diagonals are legal even when the two adjacent orthogonal cells are blocked.
- source
[[0,1,1],[1,1,1],[1,1,0]]- grid
[[0,1,1],[1,1,1],[1,1,0]]- queue
[]- distance
[[1,0,0],[0,0,0],[0,0,0]]- phase
"visit"- current
[0,0]
- The reachable open component cannot reach the destination.
Both endpoints being open does not guarantee connectivity.
- source
[[0,1,1],[1,1,1],[1,1,0]]- grid
[[0,1,1],[1,1,1],[1,1,0]]- queue
[]- distance
[[1,0,0],[0,0,0],[0,0,0]]- phase
"exhausted"- current
null
- Return the documented value, changed-grid view, fresh result, or cloned graph view.
Coordinates and object identities follow the problem-specific contract. Discovery histories are teaching views, not additional Java workspace.
- result
-1
Single open cell
Input: [[0]] · Minimum cell count / −1: 1
Step 1 of 3: Seed the open start with a one-cell path.
Distance zero means undiscovered in this separate matrix. Returned length counts cells, including start and destination.
Phase: seed.
Unchanged source grid
Coordinate queue — front at left; already claimed
- (0, 0)
Separate distances — 0 undiscovered; positive counts cells
Source 0 means open and 1 means blocked. Distances use a separate meaning: 0 undiscovered, 1 the starting cell. All eight directions are legal, including corner diagonals. At a target return, queued alternatives may remain and unvisited cells are not a complete distance map.
The exact state table and static walkthrough below provide the same information without relying on color.
| Variable | Value |
|---|---|
| source | [[0]] |
| grid | [[0]] |
| queue | [[0,0]] |
| distance | [[1]] |
| phase | "seed" |
| current | null |
See the affected Java block
1 import java.util.*; 2 public final class Solution { 3 private static int validate(int[][] grid) { 4 Objects.requireNonNull(grid,"grid");int n=grid.length; 5 for(int[] row:grid){if(row==null||row.length!=n)throw new IllegalArgumentException("expected square");for(int value:row)if(value!=0&&value!=1)throw new IllegalArgumentException("invalid cell");}return n; 6 } 7 public static int shortestPath(int[][] grid) { 8 int n=validate(grid);if(n==0||grid[0][0]!=0||grid[n-1][n-1]!=0)return -1; 9 int[][] distance=new int[n][n];ArrayDeque<int[]> queue=new ArrayDeque<>();distance[0][0]=1;queue.addLast(new int[]{0,0}); 10 while(!queue.isEmpty()) { 11 int[] cell=queue.removeFirst(); 12 if(cell[0]==n-1&&cell[1]==n-1)return distance[cell[0]][cell[1]]; 13 for(int dr=-1;dr<=1;dr++)for(int dc=-1;dc<=1;dc++) { 14 if(dr==0&&dc==0)continue;int nr=cell[0]+dr,nc=cell[1]+dc; 15 if(nr<0||nr>=n||nc<0||nc>=n||grid[nr][nc]!=0||distance[nr][nc]!=0)continue; 16 distance[nr][nc]=distance[cell[0]][cell[1]]+1;queue.addLast(new int[]{nr,nc}); 17 } 18 } 19 return -1; 20 } 21 public static int baseline(int[][] grid) { 22 int n=validate(grid);if(n==0||grid[0][0]!=0||grid[n-1][n-1]!=0)return -1; 23 int[][] distance=new int[n][n];for(int[] row:distance)Arrays.fill(row,Integer.MAX_VALUE);distance[0][0]=1; 24 boolean changed; 25 do{changed=false;int[][] next=new int[n][];for(int r=0;r<n;r++)next[r]=distance[r].clone();for(int r=0;r<n;r++)for(int c=0;c<n;c++)if(grid[r][c]==0)for(int dr=-1;dr<=1;dr++)for(int dc=-1;dc<=1;dc++){if(dr==0&&dc==0)continue;int nr=r+dr,nc=c+dc;if(nr>=0&&nr<n&&nc>=0&&nc<n&&distance[nr][nc]!=Integer.MAX_VALUE&&distance[nr][nc]+1<next[r][c]){next[r][c]=distance[nr][nc]+1;changed=true;}}distance=next;}while(changed); 26 return distance[n-1][n-1]==Integer.MAX_VALUE?-1:distance[n-1][n-1]; 27 } 28 } 29
Highlight locates the relevant statement or block; one trace step may summarize several assignments.
Read the full static trace
- Seed the open start with a one-cell path.
Distance zero means undiscovered in this separate matrix. Returned length counts cells, including start and destination.
- source
[[0]]- grid
[[0]]- queue
[[0,0]]- distance
[[1]]- phase
"seed"- current
null
- Return the first dequeued destination distance.
Pending cells may remain undispatched; FIFO already certifies the target’s minimum path length.
- source
[[0]]- grid
[[0]]- queue
[]- distance
[[1]]- phase
"target"- current
[0,0]
- Return the documented value, changed-grid view, fresh result, or cloned graph view.
Coordinates and object identities follow the problem-specific contract. Discovery histories are teaching views, not additional Java workspace.
- result
1
Empty square
Input: [] · Minimum cell count / −1: -1
Step 1 of 2: Reject empty input or a blocked endpoint after full validation.
Open is source value zero. No distance matrix is allocated on this early-return path.
Phase: empty.
Unchanged source grid
No cells.
Coordinate queue — front at left; already claimed
Empty.
Separate distances — 0 undiscovered; positive counts cells
No cells.
Source 0 means open and 1 means blocked. Distances use a separate meaning: 0 undiscovered, 1 the starting cell. All eight directions are legal, including corner diagonals. At a target return, queued alternatives may remain and unvisited cells are not a complete distance map.
The exact state table and static walkthrough below provide the same information without relying on color.
| Variable | Value |
|---|---|
| source | [] |
| grid | [] |
| queue | [] |
| distance | [] |
| phase | "empty" |
| current | null |
See the affected Java block
1 import java.util.*; 2 public final class Solution { 3 private static int validate(int[][] grid) { 4 Objects.requireNonNull(grid,"grid");int n=grid.length; 5 for(int[] row:grid){if(row==null||row.length!=n)throw new IllegalArgumentException("expected square");for(int value:row)if(value!=0&&value!=1)throw new IllegalArgumentException("invalid cell");}return n; 6 } 7 public static int shortestPath(int[][] grid) { 8 int n=validate(grid);if(n==0||grid[0][0]!=0||grid[n-1][n-1]!=0)return -1; 9 int[][] distance=new int[n][n];ArrayDeque<int[]> queue=new ArrayDeque<>();distance[0][0]=1;queue.addLast(new int[]{0,0}); 10 while(!queue.isEmpty()) { 11 int[] cell=queue.removeFirst(); 12 if(cell[0]==n-1&&cell[1]==n-1)return distance[cell[0]][cell[1]]; 13 for(int dr=-1;dr<=1;dr++)for(int dc=-1;dc<=1;dc++) { 14 if(dr==0&&dc==0)continue;int nr=cell[0]+dr,nc=cell[1]+dc; 15 if(nr<0||nr>=n||nc<0||nc>=n||grid[nr][nc]!=0||distance[nr][nc]!=0)continue; 16 distance[nr][nc]=distance[cell[0]][cell[1]]+1;queue.addLast(new int[]{nr,nc}); 17 } 18 } 19 return -1; 20 } 21 public static int baseline(int[][] grid) { 22 int n=validate(grid);if(n==0||grid[0][0]!=0||grid[n-1][n-1]!=0)return -1; 23 int[][] distance=new int[n][n];for(int[] row:distance)Arrays.fill(row,Integer.MAX_VALUE);distance[0][0]=1; 24 boolean changed; 25 do{changed=false;int[][] next=new int[n][];for(int r=0;r<n;r++)next[r]=distance[r].clone();for(int r=0;r<n;r++)for(int c=0;c<n;c++)if(grid[r][c]==0)for(int dr=-1;dr<=1;dr++)for(int dc=-1;dc<=1;dc++){if(dr==0&&dc==0)continue;int nr=r+dr,nc=c+dc;if(nr>=0&&nr<n&&nc>=0&&nc<n&&distance[nr][nc]!=Integer.MAX_VALUE&&distance[nr][nc]+1<next[r][c]){next[r][c]=distance[nr][nc]+1;changed=true;}}distance=next;}while(changed); 26 return distance[n-1][n-1]==Integer.MAX_VALUE?-1:distance[n-1][n-1]; 27 } 28 } 29
Highlight locates the relevant statement or block; one trace step may summarize several assignments.
Read the full static trace
- Reject empty input or a blocked endpoint after full validation.
Open is source value zero. No distance matrix is allocated on this early-return path.
- source
[]- grid
[]- queue
[]- distance
[]- phase
"empty"- current
null
- Return the documented value, changed-grid view, fresh result, or cloned graph view.
Coordinates and object identities follow the problem-specific contract. Discovery histories are teaching views, not additional Java workspace.
- result
-1
Blocked destination after full validation
Input: [[0,0],[0,1]] · Minimum cell count / −1: -1
Step 1 of 2: Reject empty input or a blocked endpoint after full validation.
Open is source value zero. No distance matrix is allocated on this early-return path.
Phase: blocked.
Unchanged source grid
Coordinate queue — front at left; already claimed
Empty.
Separate distances — 0 undiscovered; positive counts cells
No cells.
Source 0 means open and 1 means blocked. Distances use a separate meaning: 0 undiscovered, 1 the starting cell. All eight directions are legal, including corner diagonals. At a target return, queued alternatives may remain and unvisited cells are not a complete distance map.
The exact state table and static walkthrough below provide the same information without relying on color.
| Variable | Value |
|---|---|
| source | [[0,0],[0,1]] |
| grid | [[0,0],[0,1]] |
| queue | [] |
| distance | [] |
| phase | "blocked" |
| current | null |
See the affected Java block
1 import java.util.*; 2 public final class Solution { 3 private static int validate(int[][] grid) { 4 Objects.requireNonNull(grid,"grid");int n=grid.length; 5 for(int[] row:grid){if(row==null||row.length!=n)throw new IllegalArgumentException("expected square");for(int value:row)if(value!=0&&value!=1)throw new IllegalArgumentException("invalid cell");}return n; 6 } 7 public static int shortestPath(int[][] grid) { 8 int n=validate(grid);if(n==0||grid[0][0]!=0||grid[n-1][n-1]!=0)return -1; 9 int[][] distance=new int[n][n];ArrayDeque<int[]> queue=new ArrayDeque<>();distance[0][0]=1;queue.addLast(new int[]{0,0}); 10 while(!queue.isEmpty()) { 11 int[] cell=queue.removeFirst(); 12 if(cell[0]==n-1&&cell[1]==n-1)return distance[cell[0]][cell[1]]; 13 for(int dr=-1;dr<=1;dr++)for(int dc=-1;dc<=1;dc++) { 14 if(dr==0&&dc==0)continue;int nr=cell[0]+dr,nc=cell[1]+dc; 15 if(nr<0||nr>=n||nc<0||nc>=n||grid[nr][nc]!=0||distance[nr][nc]!=0)continue; 16 distance[nr][nc]=distance[cell[0]][cell[1]]+1;queue.addLast(new int[]{nr,nc}); 17 } 18 } 19 return -1; 20 } 21 public static int baseline(int[][] grid) { 22 int n=validate(grid);if(n==0||grid[0][0]!=0||grid[n-1][n-1]!=0)return -1; 23 int[][] distance=new int[n][n];for(int[] row:distance)Arrays.fill(row,Integer.MAX_VALUE);distance[0][0]=1; 24 boolean changed; 25 do{changed=false;int[][] next=new int[n][];for(int r=0;r<n;r++)next[r]=distance[r].clone();for(int r=0;r<n;r++)for(int c=0;c<n;c++)if(grid[r][c]==0)for(int dr=-1;dr<=1;dr++)for(int dc=-1;dc<=1;dc++){if(dr==0&&dc==0)continue;int nr=r+dr,nc=c+dc;if(nr>=0&&nr<n&&nc>=0&&nc<n&&distance[nr][nc]!=Integer.MAX_VALUE&&distance[nr][nc]+1<next[r][c]){next[r][c]=distance[nr][nc]+1;changed=true;}}distance=next;}while(changed); 26 return distance[n-1][n-1]==Integer.MAX_VALUE?-1:distance[n-1][n-1]; 27 } 28 } 29
Highlight locates the relevant statement or block; one trace step may summarize several assignments.
Read the full static trace
- Reject empty input or a blocked endpoint after full validation.
Open is source value zero. No distance matrix is allocated on this early-return path.
- source
[[0,0],[0,1]]- grid
[[0,0],[0,1]]- queue
[]- distance
[]- phase
"blocked"- current
null
- Return the documented value, changed-grid view, fresh result, or cloned graph view.
Coordinates and object identities follow the problem-specific contract. Discovery histories are teaching views, not additional Java workspace.
- result
-1
Test the contract
Input:
Empty or blocked endpoint
Output:-1Endpoint feasibility.
Input:
Single open cell
Output:1Cell-count units.
Input:
Open diagonal with blocked orthogonals
Output:2 for 2×2No corner-cut restriction.
Input:
Open endpoints separated by walls
Output:-1Reachability is still required.
Input:
316×316 all-open grid
Output:316Maximum tested square and diagonal shortest path.
Common mistakes and counterexamples
Return an edge count
Counterexample: A one-cell open grid must return 1, not 0.
Seed distance one.
Use four directions or forbid diagonal corner crossing
Counterexample: [[0,1],[1,0]] is solvable in two cells.
Implement the exact eight-neighbor contract.
Mark only after dequeueing
Counterexample: Multiple same-layer parents can enqueue one coordinate repeatedly.
Assign distance before enqueue.
Assume open endpoints imply connectivity
Counterexample: A wall band can isolate the destination.
Return -1 when the reachable frontier exhausts.
Follow-ups
Return a shortest route.
Store a parent coordinate on first discovery and reconstruct from the target. Specify neighbor order if deterministic ties matter and count route output size.
Use weighted terrain.
A FIFO does not finalize arbitrary positive costs. Change to Dijkstra or another algorithm justified by the weight domain, keeping cell-count versus cost semantics separate.
Disallow diagonal corner cutting.
Explicitly require the two corresponding orthogonal cells to be open before a diagonal move. This is a different adjacency relation and changes the two-cell example.
Your Java attempt
Java 21 · Draft only. Your code is not compiled, executed, or graded here. Run it locally against the examples and edge cases.
Saving stores text in this browser, visible to other people using this browser profile. It does not sync to your account. Loading is always explicit.
No unsaved text changes · 156/20,000 characters
Self-review
Use the checklist to test your explanation. Checks apply to this visit.