Shortest Path in a Binary Maze

You are given an R x C grid where every cell is either open (0) or blocked (1). Starting at a given source cell, you may move one step at a time to an adjacent open cell (up, down, left, or right - no diagonals). Find the length of the shortest such path, measured as the number of moves, from the source cell to a given destination cell. If the destination cannot be reached, print -1. It is guaranteed that both the source and destination cells are open.

Input: The first line contains R and C. Each of the next R lines contains C integers (0 or 1) describing one grid row. The final line contains four integers: the source row, source column, destination row, and destination column. Output: Print a single integer: the minimum number of moves from source to destination, or -1 if the destination is unreachable.

1 <= R, C <= 200; grid values are 0 (open) or 1 (blocked); all coordinates are 0-indexed

BFS is the go-to technique whenever a problem asks for the SHORTEST path in an UNWEIGHTED graph or grid (every move costs the same) - DFS finds A path, but only BFS guarantees finding the SHORTEST one, due to its level-by-level exploration order.

Find the shortest path (fewest moves) between two cells in a grid, where some cells are blocked. Brute force: Try every possible path via exhaustive DFS-based exploration, tracking the shortest one found - this works but can explore many needlessly long paths before finding the true shortest one, whereas BFS guarantees the shortest path is found the moment the destination is first reached. Optimised: BFS explores cells in order of INCREASING distance from the source (since it processes the queue level by level), guaranteeing that the very FIRST time the destination is dequeued, it's via a genuinely shortest path - no need to explore further or compare multiple paths' lengths afterward.

1. Since every move costs exactly the same (1 step), BFS guarantees that a cell is first reached via one of its GENUINELY shortest possible paths. 2. Use a queue to process cells level by level, marking a cell as visited (and recording its distance) the MOMENT it's enqueued, not when it's dequeued - this avoids enqueuing the same cell multiple times. 3. Stop as soon as the destination cell is dequeued - its recorded distance is the answer; if the queue empties first, the destination is unreachable.

Time: O(R * C) - every cell is enqueued and processed at most once. Space: O(R * C), for the BFS queue and visited tracking in the worst case.

If the source and destination coordinates are identical, the answer is 0; the destination may be completely walled off from the source, in which case the answer is -1.

Be precise about marking cells visited AT ENQUEUE TIME (not dequeue time) - marking too late is a very common bug that lets the same cell get enqueued multiple times, wasting work (though it doesn't break correctness, since BFS distances are still eventually correct - it just does more redundant work).