Proficient Level
Implement the shortestPathBinaryMatrixLength method that returns the shortest path length through a binary matrix.
The input contains an n x n binary matrix grid. A value of 0 means the cell is open, and a value of 1 means the cell is blocked.
Your task is to find the shortest path length from the top-left cell to the bottom-right cell. You may move in all eight directions: horizontal, vertical, and diagonal.
The path length counts the starting cell and the ending cell. If no valid path exists, return -1.
Example 1
Input
grid (int[][]) =
[[0,1],[1,0]]n (int) =
2Returns (int)
2Example 2
Input
grid (int[][]) =
[[0,0,0],[1,1,0],[1,1,0]]n (int) =
3Returns (int)
4Example 3
Input
grid (int[][]) =
[[1,0],[0,0]]n (int) =
2Returns (int)
-1Use BFS because every move has the same cost.
Start from the top-left cell if it is open. Explore all eight neighboring cells level by level. The first time the bottom-right cell is reached, the current distance is the shortest path length.
If the start or end cell is blocked, or BFS finishes without reaching the end, return -1.
Pseudocode:
function shortestPathBinaryMatrixLength(grid, n):
if grid[0][0] == 1 or grid[n - 1][n - 1] == 1:
return -1
queue = empty queue
push (0, 0, 1) into queue
mark (0, 0) as visited
directions = 8 possible directions
while queue is not empty:
row, col, distance = pop queue
if row == n - 1 and col == n - 1:
return distance
for each direction:
newRow = row + direction.row
newCol = col + direction.col
if position is valid, open, and not visited:
mark position as visited
push (newRow, newCol, distance + 1) into queue
return -1Ready to test your solutionRun Code checks your solution against the test cases.Shift + Enter to run