54 lines
1.4 KiB
JavaScript
54 lines
1.4 KiB
JavaScript
/*
|
|
Shortest Path in a Grid
|
|
You are located in the top-left corner of the following grid:
|
|
|
|
[[0,0,0,0,0,0,1,0,0],
|
|
[0,0,0,0,1,0,1,0,0],
|
|
[0,0,1,0,0,0,0,0,1],
|
|
[0,0,0,1,1,0,0,1,0],
|
|
[0,0,0,0,0,0,0,0,1],
|
|
[0,0,0,1,0,0,0,0,1],
|
|
[1,1,0,0,0,1,0,0,0]]
|
|
|
|
You are trying to find the shortest path to the bottom-right corner of the grid, but there are obstacles on the grid that you cannot move onto. These obstacles are denoted by '1', while empty spaces are denoted by 0.
|
|
|
|
Determine the shortest path from start to finish, if one exists. The answer should be given as a string of UDLR characters, indicating the moves along the path
|
|
|
|
NOTE: If there are multiple equally short paths, any of them is accepted as answer. If there is no path, the answer should be an empty string.
|
|
NOTE: The data returned for this contract is an 2D array of numbers representing the grid.
|
|
|
|
Examples:
|
|
|
|
[[0,1,0,0,0],
|
|
[0,0,0,1,0]]
|
|
|
|
Answer: 'DRRURRD'
|
|
|
|
[[0,1],
|
|
[1,0]]
|
|
*/
|
|
let grid;
|
|
let dest;
|
|
let solutions;
|
|
|
|
function isValidPosition(x, y) {
|
|
return grid[x][y] == 0;
|
|
}
|
|
|
|
function solve(ns, solution, x, y) {
|
|
if([x, y] == dest) {
|
|
solutions.push(solution);
|
|
return;
|
|
}
|
|
}
|
|
|
|
/** @param {NS} ns */
|
|
export async function main(ns) {
|
|
grid = [
|
|
[0, 1, 0, 0, 0],
|
|
[0, 0, 0, 1, 0]
|
|
];
|
|
dest = [grid.length - 1, grid[grid.length - 1].length - 1];
|
|
|
|
solve(ns, "", 0, 0);
|
|
} |