You are given a 2D grid of size m x n representing a maze. Each cell in the grid is either empty (0) or blocked (1).
You are also given two coordinates:
-
start = (sx, sy)
-
end = (ex, ey)
You can move from a cell to its 4-directional neighbors (up, down, left, right), but you cannot move into or through blocked cells, and you must remain inside the grid.
Return the length of the shortest path (in number of steps) from start to end. If there is no valid path, return -1.
Assumptions and details:
-
0 <= sx, ex < m
-
0 <= sy, ey < n
-
grid[sx][sy] == 0
and
grid[ex][ey] == 0
-
1 <= m, n <= 10^3
-
Time complexity should be efficient for the upper bounds (you may consider BFS or DFS-based approaches).
Input format (for reference):
-
m, n
(integers)
-
grid
as an
m x n
matrix of 0s and 1s
-
start
coordinate
-
end
coordinate
Output:
-
An integer representing the length of the shortest path, or
-1
if unreachable.