Shortest Path Through an Obstacle Grid

Given an `m` by `n` grid of zeros and ones, a start cell, and a target cell, return the length of a shortest path that never enters a cell containing one. Explain why breadth-first search is appropriate rather than stopping at the first path found by depth-first search. ### Practice Interface and Constraints Use zero-based coordinates, four-directional movement, and one unit of distance per move. These movement and output conventions make the reported point-to-point variant explicit. Return `-1` if no valid path exists or either endpoint is blocked, and return zero when the endpoints coincide on a free cell. Require a rectangular grid and in-range endpoint coordinates; reject invalid coordinates rather than treating them as a path. Numerical size bounds were not reported. For `[[0,0,1],[1,0,0]]`, start `[0,0]`, and target `[1,2]`, the answer is `3`. ### What a Strong Answer Covers Specify the queue, visited-state rule, and distance convention. Prove shortestness under unit edge costs and account for unreachable targets, blocked endpoints, and equal endpoints. State time and auxiliary space. ### Follow-up Questions How would you reconstruct a path? What algorithm would you use if entering different cells had different nonnegative costs?