1293. Shortest Path in a Grid with Obstacles Elimination

1function shortestPath(grid: number[][], k: number): number {
2    const rows = grid.length;
3    const cols = grid[0].length;
4
5// Nếu k đủ lớn để đi đường thẳng từ (0,0) đến (m-1,n-1) bất chấp mọi chướng ngại vật
6    if (k >= rows + cols - 2) return rows + cols - 2
7
8    // visited[i][j][remainK]: đã đến (i,j) với remainK lượt loại bỏ chưa
9    const vis: boolean[][][] = Array.from({
10        length: rows
11    }, () => Array.from({ length: cols }, () => Array(k + 1).fill(false)))
12
13    const queue: [number, number, number, number][] = [];
14    queue.push([0, 0, 0, k])
15    const dirs = [
16        [1, 0], [-1, 0], [0, 1], [0, -1]
17    ]
18
19    while (queue.length > 0) {
20        const [row, col, steps, remain_k] = queue.shift()!;
21        if (row === rows - 1 && col === cols - 1) return steps;
22
23        for (const [dx, dy] of dirs) {
24            const new_r = dx + row
25            const new_c = dy + col;
26
27            if (new_r >= 0 && new_r < rows && new_c >= 0 && new_c < cols) {
28                const new_remain_k = remain_k - grid[new_r][new_c];
29                if (new_remain_k >= 0 && !vis[new_r][new_c][new_remain_k]) {
30                    vis[new_r][new_c][new_remain_k] = true;
31                    queue.push([new_r, new_c, steps + 1, new_remain_k])
32                }
33            }
34        }
35    }
36
37    return -1;
38};
39