296. Find Shortest Safe Route in a Path With Landmines

Given an n x m grid where each cell is 1 (safe) or 0 (a landmine), find the length, in cells visited (including both endpoints), of the shortest route from any safe cell in the first column to any safe cell in the last column, moving only up, down, left, or right one cell at a time. A landmine cell and every cell adjacent to it (up, down, left, right) are unsafe and can never be stepped on, including cells in the first or last column. Print -1 if no safe route exists.

Input: The first line contains an integer n. The second line contains an integer m. The next n lines each contain m space-separated integers (0 or 1), the grid. Output: Print a single integer - the length in cells of the shortest safe route from the first to the last column, or -1 if none exists.

1 <= n, m <= 50

Multi-source BFS (seeding the queue with MULTIPLE valid starting points at once) is a broadly reusable technique whenever a problem asks for the shortest distance from ANY of several valid starting positions to a target - much more efficient than running BFS separately from each one.

In a grid sprinkled with landmines (and their neighboring cells also unsafe), find the shortest safe path from the first column to the last. Brute force: Try every possible path from every starting cell individually via DFS/backtracking, tracking the shortest found - this works but is much less direct than BFS, which is purpose-built for shortest-path-in-unweighted-graph problems and naturally finds the answer without exploring every possible path. Optimised: A MULTI-SOURCE BFS (seeding the queue with every valid starting cell at once, rather than running separate single-source BFS per starting cell) explores all possible starting points simultaneously in lockstep - the FIRST time any last-column cell is dequeued is guaranteed to be via the globally shortest path from ANY valid start, since BFS processes cells in strict order of increasing distance.

For each safe cell in the first column individually, run a standard single-source BFS over the grid (treating landmine cells and their neighbors as blocked) to find the shortest distance to the nearest safe cell in the last column, then take the minimum over all starting cells' results. Each individual BFS correctly finds that start's shortest route by exploring in order of increasing distance, but repeating a full BFS once per starting cell duplicates a lot of shared work when the first column has many safe cells. Time: O(k * n * m) where k = safe first-column cells Space: O(n * m)

Starting from each safe cell in the first column, recursively explore every possible sequence of up/down/left/right moves to unvisited safe cells, tracking the path length, until reaching any safe cell in the last column, then backtrack (un-mark the cell) whenever a branch dead-ends, recording the shortest such path length found across all explored paths and all starting cells. This explores exponentially many paths since it doesn't prioritize shorter routes first, only exhaustively tries all of them. Time: O(4^(n*m)) Space: O(n * m)

Run a single BFS initialized with every safe cell in the first column simultaneously (each at distance 1), marking them visited, then expand outward level by level to unvisited safe neighbors. Because BFS processes cells in non-decreasing order of distance from the nearest source, the first time any safe cell in the last column is dequeued, its distance is guaranteed to be the overall shortest route from any starting cell, found in a single traversal instead of many. Time: O(n * m) Space: O(n * m)

1. First, mark every landmine cell AND all its up/down/left/right neighbors as unsafe (a cell might become unsafe for more than one reason, but that doesn't matter - it's just unsafe). 2. Run a MULTI-SOURCE BFS starting simultaneously from every safe cell in the first column. 3. Stop the moment any safe cell in the last column is reached - since BFS explores in strict order of distance, this is automatically the shortest possible route.

Time: O(n*m) - each cell is visited and enqueued at most once during the BFS. Space: O(n*m), for the visited/unsafe tracking grid and the BFS queue.

Test n = m = 1, grids where landmines block the entire first or last column (route impossible, -1), and n = m = 50 for performance.

Be ready to explain why 'landmine's neighbors are also unsafe' needs to be precomputed ONCE upfront (marking a whole danger zone) before running BFS - trying to check this condition ad-hoc during the BFS traversal itself would be more error-prone and repeat the same neighbor checks unnecessarily.