Queue Deque Simulation
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) = 2
Return:
(int) 2
Example 2
Input:
grid (int[][]) = [[0,0,0],[1,1,0],[1,1,0]]
n (int) = 3
Return:
(int) 4
Example 3
Input:
grid (int[][]) = [[1,0],[0,0]]
n (int) = 2
Return:
(int) -1

Use 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 -1
Run your code to see the result.