378. Search in a Maze

Given a rows x cols grid of 0s (blocked) and 1s (open), a source cell, and a destination cell, print 'Yes' if there is a path from source to destination moving only 4-directionally through open cells, otherwise print 'No'.

Input: The first line contains two integers rows and cols. Each of the next rows lines contains cols space-separated values (0 or 1), the grid. This is followed by a line with the source cell's row and column, then a line with the destination cell's row and column. Output: Print 'Yes' if a path exists from source to destination through open cells, otherwise print 'No'.

1 <= rows, cols <= 1000

This is one of the most foundational 'grid as graph' problems - recognizing that ANY grid can be treated as a graph (cells as nodes, adjacency as edges) unlocks applying every standard graph algorithm (BFS, DFS, and more) directly to grid problems.

Check whether a path exists between two cells in a grid, moving only through open cells. Brute force: Try every possible sequence of moves via exhaustive search without tracking visited cells - this can loop forever on grids with cycles (open loops of cells), never terminating. Optimised: A standard BFS/DFS with visited-cell tracking guarantees termination (every cell visited at most once) and correctly determines reachability, exactly as it would for any general graph - a grid is simply a graph where nodes are cells and edges connect 4-directional open neighbors.

Starting from the source cell, recursively try moving to each of the 4 neighboring cells that is in-bounds, open, and not yet visited, marking cells visited as they're entered so the same cell isn't explored twice; if any recursive path reaches the destination, the answer is 'Yes'. Marking visited cells keeps this from looping forever, so it correctly explores the whole reachable region, but doing this via language-level recursion means the call stack depth can reach into the hundreds of thousands for a 1000x1000 grid, risking a stack overflow. Time: O(rows * cols) Space: O(rows * cols)

Run two breadth-first searches at once, one expanding outward from the source and one expanding outward from the destination, alternating which one advances a level at a time, and stop as soon as the two frontiers touch (reachable) or both are exhausted without meeting (unreachable). Searching from both ends simultaneously has the same worst-case bound as a single BFS/DFS over the whole grid, but the two frontiers together typically cover a much smaller region before meeting than a single search sweeping the entire grid would, which matters when rows and cols are both up to 1000. Time: O(rows * cols) Space: O(rows * cols)

Use the same depth-first exploration and visited-marking logic as the recursive version, but manage the frontier with an explicit stack data structure living on the heap instead of relying on the language's call stack. This produces identical results to the recursive DFS and the same total work, but removes any risk of a stack-overflow crash on large grids, since a heap-allocated stack can grow far larger than the call stack safely allows. Time: O(rows * cols) Space: O(rows * cols)

1. Treat this as plain BFS/DFS on the grid, where open cells are nodes and 4-directionally-adjacent open cells are edges. 2. If the SOURCE or DESTINATION cell itself is blocked, the answer is immediately No, regardless of the rest of the grid. 3. Track visited cells to avoid revisiting them - without this, DFS could loop forever on grids containing cycles.

Time: O(rows * cols) - every cell is visited at most once during the traversal. Space: O(rows * cols), for the visited-tracking grid and the BFS queue or DFS recursion stack.

Test the source or destination cell itself being blocked (0), source equal to destination, and rows/cols at the upper bound of 1000.

Be ready to check the source/destination-blocked edge case FIRST, before even starting any traversal - a surprisingly common oversight that can cause an otherwise-correct BFS/DFS to give a subtly wrong answer.