1293. Shortest Path in a Grid with Obstacles Elimination
Tags:
Hard
Skills:
BFS
June 24, 2025
04:32 AM
No headings found
Loading content...
Related Posts
Leetcode
No headings found
Related Posts
Leetcode
Problem
Bài toán yêu cầu tìm đường đi ngắn nhất từ góc trên trái đến góc dưới phải của grid, cho phép loại bỏ tối đa k chướng ngại vật (ô giá trị 1). Nếu không thể đi tới đích return -1
Approach
visited[i][j][remainK] để tránh lặp lại trạng thái đã thăm với số chướng ngại vật còn lại lớn hơn.Time and space complexity
Solution
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Điều kiện if (k >= m + n - 2) return m + n - 2; xuất hiện trong lời giải vì lý do sau: