298. Longest Possible Route in a Matrix With Hurdles

Given an n x m grid where each cell is 1 (open) or 0 (a hurdle), and a source and destination cell (both guaranteed open), find the length, in moves, of the longest simple route from source to destination that moves only up, down, left, or right through open cells and never revisits a cell. Print -1 if the destination is unreachable.

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). This is followed by a line with the source cell's row and column, and a line with the destination cell's row and column. Output: Print a single integer - the length in moves of the longest simple route from source to destination, or -1 if unreachable.

1 <= n, m <= 8

This is a clear example of a problem where the SMALL constraint size (8x8 grid) is the tell that an exponential backtracking search is not just acceptable but the INTENDED solution - a fundamentally different signal than the shortest-path landmine problem, which uses BFS specifically because shortest-path search IS efficiently solvable.

Find the length of the longest simple route (no cell revisited) between two points in a grid, moving through open cells only. Brute force: There isn't really a 'faster' alternative distinct from this exhaustive backtracking search - finding the LONGEST simple path (as opposed to the shortest) in a graph is a genuinely hard problem in general, and exhaustive search with backtracking is the standard, necessary approach given the small grid size constraint (up to 8x8). Optimised: Backtracking (unmarking a cell as visited after fully exploring all paths through it) is essential here, unlike a simple one-way traversal, because the SAME cell might be part of MANY different candidate routes being explored - marking it permanently visited would incorrectly block off other valid routes that could also pass through it.

Extend the backtracking search with a bound: at each step, quickly check (e.g. via a fast flood-fill from the current cell over still-unvisited open cells) whether the destination is even still reachable, and separately whether the maximum possible remaining path length from here could beat the best length found so far; if not, prune that branch immediately instead of exploring it further. Because finding the longest simple path is NP-hard in general, no polynomial algorithm exists, but since the grid is capped at 8x8 this pruning discards the vast majority of dead branches early, making the search practically fast despite the same exponential worst-case bound. Time: O(4^(n*m)) worst case, heavily pruned in practice Space: O(n*m)

Use the same backtracking search but explore neighbor directions in a fixed sensible order and immediately skip any neighbor that's out of bounds, a hurdle, or already visited before recursing (rather than recursing and immediately returning). This trims a meaningful fraction of wasted recursive calls in practice compared to the brute approach, though it doesn't change the exponential worst case since longest simple path is inherently a hard combinatorial search. Time: O(4^(n*m)) Space: O(n*m)

Do a plain DFS/backtracking search from the source: mark the current cell visited, recurse into every open, in-bounds, unvisited neighbor, and when the destination is reached compare the current path length to the best found so far, then unmark the cell (backtrack) before trying the next neighbor. This explores every simple path in the grid with no attempt to cut off branches that clearly can't beat the current best. Time: O(4^(n*m)) Space: O(n*m) recursion stack and visited grid

1. DFS/backtrack from the source: mark the current cell as visited, then try every open, unvisited neighbor in each of the 4 directions. 2. Whenever a path successfully reaches the destination, record its length if it's the longest found so far. 3. UNMARK (backtrack) the current cell as unvisited before returning from the recursive call, so a DIFFERENT route can still pass through it later.

Time: Exponential in the worst case (up to 4^(n*m) in the loosest bound, though heavily pruned by the visited-cell and boundary/hurdle checks) - only tractable because of the small grid size constraint (n, m <= 8). Space: O(n*m) for the visited-tracking grid and the recursion stack.

Test the source equal to the destination, a destination surrounded by hurdles (unreachable, -1), and n = m = 8 (largest case, since enumerating simple paths is exponential).

Be ready to explain clearly why finding the LONGEST simple path is fundamentally harder than finding the SHORTEST one (which BFS solves efficiently) - longest simple path is NP-hard in general graphs, which is exactly why exhaustive backtracking (rather than some clever polynomial algorithm) is the expected approach here, justified by the small constraint.