Maze Path Finding with Obstacles

Problem Given a grid maze with obstacles, a source cell, and a destination cell, find a path between them — or the shortest such path (clarify which; it changes the algorithm).

Input / Output

• Input: m x n grid (0 free / 1 obstacle), start, target.
• Output: path as a cell sequence, its length, or existence boolean.

Constraints

• Up to 10^3 x 10^3 grid; 4-directional moves unless stated otherwise.

Example

• [[0,0,1],[0,1,0],[0,0,0]], (0,0) → (2,2): shortest path length 4 via the left column and bottom row.

Expected approach

• Shortest path in an unweighted grid → BFS from the source, marking visited on enqueue, recording parent pointers to reconstruct the path; O(m*n) time/space. Any-path/existence → DFS works but gives non-optimal paths. Say why DFS isn't shortest and why Dijkstra is overkill (unit weights). Variants worth knowing: 8-direction moves, weighted cells (Dijkstra/0-1 BFS), one-obstacle-elimination (state = cell + eliminations used).