Below is a Python implementation for the “Shortest Path in Binary Matrix” problem with comments:

from typing import List
from collections import deque

def shortest_path_binary_matrix(grid: List[List[int]]) -> int:
    # Check if the top-left or bottom-right cells are obstacles, indicating no path
    if grid[0][0] == 1 or grid[-1][-1] == 1:
        return -1

    rows, cols = len(grid), len(grid[0])
    
    # Directions for moving horizontally, vertically, or diagonally
    directions = [(1, 0), (0, 1), (-1, 0), (0, -1), (1, 1), (-1, -1), (1, -1), (-1, 1)]
    
    # Using deque for Breadth-First Search (BFS)
    queue = deque([(0, 0, 0)])  # (row, col, distance)
    
    while queue:
        row, col, distance = queue.popleft()
        
        # Check if we reached the bottom-right cell
        if (row, col) == (rows - 1, cols - 1):
            return distance
        
        # Explore all possible directions
        for dr, dc in directions:
            new_row, new_col = row + dr, col + dc
            
            # Check if the new position is within bounds and not an obstacle and not visited
            if 0 <= new_row < rows and 0 <= new_col < cols and grid[new_row][new_col] == 0:
                # Mark the cell as visited by setting it to 2
                grid[new_row][new_col] = 2
                # Add the new position to the queue with updated distance
                queue.append((new_row, new_col, distance + 1))
    
    # If the queue is empty and we haven't reached the destination, there is no path
    return -1

# Example usage:
grid1 = [[0,0],[0,0]]
res1 = shortest_path_binary_matrix(grid1)
print(res1)
assert res1 == 1, "The result should be 1"

grid2 = [[0,0,0],[1,1,0],[0,0,0],[0,1,1],[0,0,0]]
res2 = shortest_path_binary_matrix(grid2)
print(res2)
assert res2 == 6, "The result should be 6"

grid3 = [[0,0,0],[1,1,0],[0,1,1]]
res3 = shortest_path_binary_matrix(grid3)
print(res3)
assert res3 == -1, "The result should be -1"

grid4 = [[0,0],[1,1],[0,0]]
res4 = shortest_path_binary_matrix(grid4)
print(res4)
assert res4 == -1, "The result should be -1"

Time Complexity:

  • In the worst case, every cell in the matrix needs to be visited once.
  • Each cell is processed in constant time during BFS.
  • Therefore, the time complexity is O(rows * cols).

Space Complexity:

  • The space complexity is determined by the queue used in BFS.
  • In the worst case, the queue can contain all cells in the matrix.
  • Therefore, the space complexity is O(rows * cols).