Longest route in a matrix with hurdles / all paths top-left to bottom-right

Medium

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

Your solution ✓ Solved

Ctrl/⌘ + Enter to run
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).