Given a binary matrix representing an obstacle grid where 0 represents an empty cell and 1 represents an obstacle, find the length of the shortest path from the top-left corner (0, 0) to the bottom-right corner (m-1, n-1). If there is no path, return -1.

You can only move to adjacent cells horizontally, vertically, or diagonally. The path cannot cross through obstacles.

Function Signature:

from typing import List

def shortest_path_binary_matrix(grid: List[List[int]]) -> int:
    """
    Find the length of the shortest path in the binary matrix.

    Parameters:
    - grid: A binary matrix representing an obstacle grid.

    Returns:
    - int: The length of the shortest path, or -1 if there is no path.
    """
    # Your code here

Example:

# 0 0
# 0 0
grid1 = [[0,0],[0,0]]
res1 = shortest_path_binary_matrix(grid1)
print(res1)
assert res1 == 1, "The result should be 1"
# Explanation: The shortest path is (0,0) -> (1,1).

# 0 0 0
# 1 1 0
# 0 0 0
# 0 1 1
# 0 0 0
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"
# Explanation: The shortest path is (0,0) -> (0,1) -> (1,2) -> (2,1) -> (3,0) -> (4,1) -> (4,2).

# 0 0 0
# 1 1 0
# 0 1 1
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"
# Explanation: There is no path from (0,0) to (2,2) due to obstacles in (2,2).

# 0 0
# 1 1
# 0 0
grid4 = [[0,0],[1,1],[0,0]]
res4 = shortest_path_binary_matrix(grid4)
print(res4)
assert res4 == -1, "The result should be -1"
# Explanation: There is no path from (0,0) to (2,2) due to obstacles in the middle.

Note:

  • The input matrix will be a binary matrix where 0 represents an empty cell, and 1 represents an obstacle.
  • The top-left corner (0, 0) and the bottom-right corner (m-1, n-1) are always empty cells.
  • You can only move to adjacent cells horizontally, vertically, or diagonally.
  • If there is no path, return -1.

Instructions:

  • Write the shortest_path_binary_matrix function to solve the problem.
  • Implement your solution in Python.
  • Provide clear comments in your code.
  • Discuss the time and space complexity of your solution.