Find shortest path in a grid with obstacles

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.

Shortest Path in a Grid with Obstacles

You are given a 2D grid of size m x n representing a maze. Each cell is either empty (0) or blocked (1).

You are also given two coordinates:

• start = (sx, sy)
• end = (ex, ey)

From a cell you may move to its 4-directional neighbors (up, down, left, right). You cannot move into or through a blocked cell, and you must stay inside the grid.

Return the length of the shortest path (in number of steps) from start to end. If no valid path exists, return -1. A path's length is the number of moves; the path from a cell to itself has length 0.

Example

grid = [[0,0,0],
        [0,1,0],
        [0,0,0]]
start = (0,0), end = (2,2)  ->  4

One shortest route is (0,0) -> (1,0) -> (2,0) -> (2,1) -> (2,2), which is 4 steps.

Constraints

• 1 <= m, n <= 10^3
• Each grid cell is 0 (empty) or 1 (blocked)
• 0 <= sx, ex < m and 0 <= sy, ey < n
• grid[sx][sy] == 0 and grid[ex][ey] == 0
• Movement is 4-directional only (no diagonals)

Hints

1. Shortest path in an unweighted grid where every move costs 1 is the textbook case for breadth-first search (BFS), not DFS — BFS visits cells in increasing distance order, so the first time you reach the target you have the minimum number of steps.
2. Track a visited matrix so each cell is enqueued at most once; this keeps the whole traversal O(m*n) even for the 1000x1000 upper bound.
3. Handle the degenerate case where start == end (answer 0) before the search, and remember to return -1 when the queue empties without reaching the target.