LeetCode网格中的最短路径_leetcode 找到两个点之间的最短路径

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/shortest-path-in-a-grid-with-obstacles-elimination
给你一个 m * n 的网格，其中每个单元格不是 0（空）就是 1（障碍物）。每一步，您都可以在空白单元格中上、下、左、右移动。
如果您 最多 可以消除 k 个障碍物，请找出从左上角 (0, 0) 到右下角 (m-1, n-1) 的最短路径，并返回通过该路径所需的步数。如果找不到这样的路径，则返回 -1。
示例 1：
输入：
grid =
[[0,0,0],
[1,1,0],
[0,0,0],
[0,1,1],
[0,0,0]],
k = 1
输出：6
解释：
不消除任何障碍的最短路径是 10。
消除位置 (3,2) 处的障碍后，最短路径是 6 。该路径是 (0,0) -> (0,1) -> (0,2) -> (1,2) -> (2,2) -> (3,2) -> (4,2).
示例 2：
输入：
grid =
[[0,1,1],
[1,1,1],
[1,0,0]],
k = 1
输出：-1
解释：
我们至少需要消除两个障碍才能找到这样的路径。
提示：
grid.length == m
grid[0].length == n
1 <= m, n <= 40
1 <= k <= m*n
grid[i][j] == 0 or 1
grid[0][0] == grid[m-1][n-1] == 0
思路：我的思路是将当前状态走过的点以及消除的障碍物给记录下来，但是这样的话点太多了，队列放不下。因为一个点可以多次走过（对于每一条路，只要没走过他都可以走）。
正解：我们可以定义一个初始状态f[0][0][k]这样就代表该(0,0)点还有k个可以消除，所以就可以直接判断当前的点状态k，如果走过就没必要再走了。这是本题的关键。其余的就是bfs了。

class Solution {
public:
    struct node{
        int x;
        int y;
        int k;
        int step;
    }q[1000000];
    bool f[41][41][16001];
    int head = 0, tail = 1, x, y, m, n, i, j, l, shu;
    int dx[4]={0, 1, 0, -1},dy[4]={1, 0, -1, 0};
    int shortestPath(vector<vector<int>>& grid, int k) {
        m = grid.size();
        n = grid[0].size();
        if (m == 1 && n == 1) return 0;
        q[1].x = 0;
        q[1].y = 0;
        q[1].k = k;
        f[0][0][k] = true;//当前状态就是坐标＋还能消掉多少障碍物
        while (head < tail){
            head++;
            x = q[head].x;
            y = q[head].y;
            for (i = 0; i < 4; i++){
                shu = q[head].k;
                if (x + dx[i] >=0 && x + dx[i] < m && y + dy[i] >= 0 && y + dy[i] < n){
                    if (grid[x+dx[i]][y+dy[i]] == 1){
                         shu--;
                    }
                    if (shu < 0) continue;
                    if (f[x+dx[i]][y+dy[i]][shu] == true) continue;
                    tail++;
                    q[tail].step = q[head].step + 1;
                    q[tail].x = x + dx[i]; 
                    q[tail].y = y + dy[i];
                    f[x + dx[i]][y + dy[i]][shu] = true;
                    q[tail].k = shu;
                    if (x + dx[i] == m - 1 && y + dy[i] == n - 1 && q[tail].k >= 0 ){
                        return q[tail].step;
                    }
                }
            }
        }
        return -1;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46