Problems178
Search for a command to run...
Every path through a maze, corner to corner
Initialization
From each cell try up, left, down, right in that order, appending the move to the path string. Reaching the bottom-right corner records the path; anything else backtracks and restores the cell.
DFS with Backtracking
1function path(m, x, y, dir, n, result) {2 // Destination reached3 if (x === n - 1 && y === n - 1) {4 result.push(dir);5 return;6 }7 8 // Blocked, or already on this path9 if (m[x][y] === 0) return;10 11 // Mark visited12 m[x][y] = 0;13 14 if (x > 0) path(m, x - 1, y, dir + 'U', n, result);15 if (y > 0) path(m, x, y - 1, dir + 'L', n, result);//n: 5paths: 016 if (x < n - 1) path(m, x + 1, y, dir + 'D', n, result);17 if (y < n - 1) path(m, x, y + 1, dir + 'R', n, result);18 19 // Restore on the way out20 m[x][y] = 1;21}22 23function findPath(grid) {24 const n = grid.length;25 const result = [];26 if (grid[0][0] === 0 || grid[n - 1][n - 1] === 0) return result;27 path(grid, 0, 0, "", n, result);28 return result.sort();29}