https://leetcode.com/problems/find-the-safest-path-in-a-grid/
I thought this problem was not so difficult but it is completely wrong.
This solution is TLE. This is my limit.
var maximumSafenessFactor = function (grid) {
// dgrid
let n = grid.length;
let dgrid = new Array(n).fill(0).map(() => new Array(n).fill(Infinity));
let out = (i, j, n) => i < 0 || i >= n || j < 0 || j >= n;
let goal = (i, j, n) => i === n - 1 && j === n - 1;
let around = (i, j) => [
[i - 1, j],
[i + 1, j],
[i, j - 1],
[i, j + 1],
];
let fill = (dgrid, i, j, v) => {
let n = grid.length;
if (out(i, j, n)) return;
if (v < 0) return;
if (dgrid[i][j] <= v) return;
dgrid[i][j] = v;
for (let [ni, nj] of around(i, j)) {
fill(dgrid, ni, nj, v + 1);
}
};
for (let i = 0; i < n; i++) {
for (let j = 0; j < n; j++) {
fill(dgrid, i, j, grid[i][j] - 1);
}
}
let reachable = (dgrid, min) => {
let n = dgrid.length;
let pgrid = new Array(n).fill(0).map(() => new Array(n).fill(Infinity));
let stack = [[0, 0, 0]];
while (stack.length) {
let [i, j, v] = stack.pop();
if (out(i, j, n)) continue;
if (dgrid[i][j] < min) continue;
if (v >= pgrid[i][j]) continue;
pgrid[i][j] = v;
stack = stack.concat(around(i, j).map(([i, j]) => [i, j, v + 1]));
}
return isFinite(pgrid[n - 1][n - 1]);
};
let min = Math.min(dgrid[0][0], dgrid[n - 1][n - 1]);
while (min) {
if (reachable(dgrid, min)) return min;
min -= 1;
}
return min;
};
I will study other solutions.