Longest route in a matrix with hurdles / all paths top-left to bottom-right
Problem
(1) Longest route: in a grid of 1 (open) and 0 (hurdle), return the length of the longest path from source to destination that never revisits a cell, or −1 if there is none. (2) All paths: print every path from the top-left to the bottom-right corner of an m × n grid, moving only right or down.
Example 1
Input: all paths in [[1,2,3], [4,5,6]] Output: 1 4 5 6, 1 2 5 6, 1 2 3 6
Also asked as: Longest Possible Route in a Matrix with Hurdles · Print all possible paths from top left to bottom right of a mXn matrix
Test cases
Case 1
Input: [[1,1,1,1,1,1,1,1,1,1],[1,1,0,1,1,0,1,1,0,1],[1,1,1,1,1,1,1,1,1,1]], 0, 0, 1, 7 Expected: 24
Case 2
Input: [[1,1],[1,1]], 0, 0, 1, 1 Expected: 2
Case 3
Input: [[1,0],[0,1]], 0, 0, 1, 1 Expected: -1
Case 4
Input: [[1]], 0, 0, 0, 0 Expected: 0
View solutionHide solution1 approach
1. DFS with a visited grid, maximise / collect on reaching the target
Time O(4^(R·C))Space O(R·C)
From each cell recurse into the 4 open, unvisited, in-bounds neighbours; mark on entry, unmark on exit. Track the longest length (or push the path) when you hit the destination.
function longestRoute(grid, sr, sc, dr, dc) { const R = grid.length, C = grid[0].length; const vis = Array.from({ length: R }, () => Array(C).fill(false)); let best = -1; const dirs = [[1,0],[-1,0],[0,1],[0,-1]]; const dfs = (r, c, len) => { if (r === dr && c === dc) { best = Math.max(best, len); return; } for (const [ddr, ddc] of dirs) { const nr = r + ddr, nc = c + ddc; if (nr >= 0 && nc >= 0 && nr < R && nc < C && grid[nr][nc] === 1 && !vis[nr][nc]) { vis[nr][nc] = true; dfs(nr, nc, len + 1); vis[nr][nc] = false; } } }; vis[sr][sc] = true; dfs(sr, sc, 0); return best;}All paths (only moving right/down) is simpler: recurse pushing "R"/"D" until you reach (m−1, n−1).