本文共 10314 字，大约阅读时间需要 34 分钟。

BFS广搜+贪心 leetcode 1293. 网格中的最短路径

 

题目描述

leetcode 1293. 网格中的最短路径

给你一个 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 来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/shortest-path-in-a-grid-with-obstacles-elimination 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

概述

典型的BFS算法是通过队列按顺序存储层级搜索，即每个层级都搜索一遍，如图的最佳路径搜索，网格最小步数搜索等一般使用BFS。

通用的BFS代码模板：

// 节点访问标识,访问过的节点无需访问（剪枝）int[][] visited = new int[m][n];// 队列初始化Queue
   
     queue = new LinkedList();// 【第1步】将起点加入队列, 非空进入循环queue.add(第一个数据)while(!queue.isEmpty()) {    // 【第2步】 获取当前队列长度即同一层级（辈分）节点个数，并遍历    int size = queue.size(); // 一定要先获取，queue后面要加入下一层级节点    for (int i = 0; i < size; i++) {        // 【第3步】 对同一层级节点逐个寻找下一层有效**路径节点**，找到目标直接返回结果终止搜索。        Node node = queue.poll();        // 下一层节点 比如网格上下左右移动        Node nextNode = node.x + xj;        //  1. 不符合要求的下一层节点直接过滤（比如越界、已经被visited[][]标记访问了）        //  2. 找到目标节点 直接返回结果        //  3. 符合要求的下一层节点放入队列        queue.offer(nextNode)    }}// 【第4步】 BFS搜索完成没找到结果，返回-1return -1;
   

题目类型扩展：

1. 若题目要求求解最小层级搜索（节点间距离固定为1），通过统计层级计数，遇到终止条件终止即可。
2. 若节点间有加权值，求解最短路径时可以在Node中增加cost记录，比较获取最佳值
3. 若需要求解最短路径，可以逆向根据visited访问记录情况回溯

方法一：visited访问标记数组二维 + 贪心 （推荐）

本题精髓在于对标记访问数组 visited值的扩展，常规0|1标记是否访问，但还需要记录走到当前位置所剩的消除障碍物机会，越多越好。因为后面的路障谁都不清楚够不够用。

class Solution {    public int shortestPath(int[][] grid, int k) {        int m = grid.length;        int n = grid[0].length;        // 非法参数处理        if (validateInputParams(k, m, n)) {            return -1;        }        // 特殊场景处理        if (m == 1 && n == 1) {            return 0;        }        // BFS对于当前点的下一个点选择，如果grid[i][j]=0则有效入队列 visited[i][j]记录消除障碍次数        // 若grid[i][j]=1则看是否还有消除障碍机会，若没有 此点丢弃        // 若有消除障碍机会， （上一个点剩余消除障碍机会 - 1）比visited[i][j] 值比大 此点入队， 小则丢弃（贪心）        // 例子：k=1, 坐标(0,2)可以为消除(0,1)障碍过来的 visited[0][2] = 0，搜索层级为2        // 也可能为不消除任何障碍过来的 visited[0][2] = 1，层级为6，更新visited[0][2] = 1并入队        // 因为到后面还需要消除障碍才能到达目标，先消除障碍走到visited[0][2] = 0的肯定到不了目标...        // 0 1 0 0 0 1 0 0        // 0 1 0 1 0 1 0 1        // 0 0 0 1 0 0 1 0                // 二维标记数组初始状态为-1，值记录剩余消除障碍的次数，剩余次数越多 越有价值（此处贪心，记录局部最优）        int[][] visited = new int[m][n];        for (int i = 0; i < m; i++) {            for (int j = 0; j < n; j++) {                visited[i][j] = -1;            }        }        // 初始步数为0，m=n=1的特殊场景已处理        int minSteps = 0;        // 初始位置标记已访问,值记录剩余消除障碍物次数  越多越好        // 1. 对于其他路径到达此点且剩余消除障碍物次数小于等于当前值 —— 剪枝        // 2. 对于其他路径到达此点且剩余消除障碍物次数大于当前值 —— 取代并入队        visited[0][0] = k;        Queue
   
     queue = new LinkedList<>();        Point startPoint = new Point(0, 0, 0);        queue.offer(startPoint);                // 定义四个方向移动坐标        int[] dx = {1, -1, 0, 0};        int[] dy = {0, 0, 1, -1};        // BFS搜索-队列遍历        while (!queue.isEmpty()) {            minSteps++;            // BFS搜索-遍历相同层级下所有节点            // 当前队列长度一定要在循环外部定义，循环内部有插入对列操作            int size = queue.size();            for (int i = 0; i < size; i++) {                Point current = queue.poll();                int x = current.x;                int y = current.y;                int oneCount = current.oneCount;                // 对当前节点四个方向进行识别处理                for (int j = 0; j < 4; j++) {                    int xNew = x + dx[j];                    int yNew = y + dy[j];                    // 越界判断                    if (xNew < 0 || xNew >= m || yNew < 0 || yNew >= n) {                        continue;                    }                    // 搜索到目标节点直接返回结果，按层级就是最短步数                    if (xNew == m - 1 && yNew == n - 1) {                        return minSteps;                    }                    // 穿越障碍次数已满                    if (grid[xNew][yNew] == 1 && oneCount >= k) {                        continue;                    }                    int oneCountNew = grid[xNew][yNew] == 1 ? oneCount + 1 : oneCount;                    // 剪枝 - 节点已被访问过，且当前visited记录的剩余障碍物消除次数 >= 当前搜索节点层级的剩余消除次数                    if (visited[xNew][yNew] != -1 && visited[xNew][yNew] >= k - oneCountNew) {                        continue;                    } else {                        // 否则，贪心将最优值更新，并将该层级节点入队                        visited[xNew][yNew] = k - oneCountNew;                    }                    queue.offer(new Point(xNew, yNew, oneCountNew));                }            }        }        // BFS没搜索到目标，返回-1        return -1;    }    private boolean validateInputParams(int k, int m, int n) {        return m > 40 || m < 1 || n > 40 || n < 1 || k < 1 || k > m * n;    }    class Point {        int x;        int y;        int oneCount;        public Point(int x, int y, int oneCount) {            this.x = x;            this.y = y;            this.oneCount = oneCount;        }    }}
   

方法二：visited访问标记数组三维扩展 （用于比较）

本题比较麻烦些，增加了障碍物且可以有k次机会消除，单纯有障碍物就是标准的BFS处理即可，但有k次消除障碍物，就需要增加一个维度来记录同一个节点被访问的时候 已经使用消除障碍物的次数。：

public int shortestPath(int[][] grid, int k) {        int m = grid.length;        int n = grid[0].length;        // 非法参数处理        if (validateInputParams(k, m, n)) {            return -1;        }        // 特殊场景处理        if (m == 1 && n == 1) {            return 0;        }        // BFS搜索节点访问标识, 此题要求有k个消除障碍的机会，所以每个节点除了标记是否被访问过        // 还要记录搜索到此节点时消除了几个障碍。消除相同障碍的下一层节点 可以剪枝（因为有相同代价更早的节点了）        // 例子：k=1, BFS是按层级来的，绕道的层级扩展越多        // 坐标(0,2)可以为消除(0,1)障碍过来的 visited[0][2][1] = 1，搜索层级为2        // 也可能为不消除任何障碍过来的 visited[0][2][0] = 1，层级为6，为扩展搜索不通障碍消除数提供区分        // 0 1 0 0 0 1 0 0        // 0 1 0 1 0 1 0 1        // 0 0 0 1 0 0 1 0        // 二维标记位置，第三维度标记 到此节点的路径处理障碍总个数        int[][][] visited = new int[m][n][k+1];        // 初始步数为0，m=n=1的特殊场景已处理        int minSteps = 0;        // 初始位置标记已访问        visited[0][0][0] = 1;        Queue
   
     queue = new LinkedList<>();        Point startPoint = new Point(0, 0, 0);        queue.offer(startPoint);        // 定义四个方向移动坐标        int[] dx = {1, -1, 0, 0};        int[] dy = {0, 0, 1, -1};        // BFS搜索-队列遍历        while (!queue.isEmpty()) {            minSteps++;            // BFS搜索-遍历相同层级下所有节点            // 当前队列长度一定要在循环外部定义，循环内部有插入对列操作            int size = queue.size();            for (int i = 0; i < size; i++) {                Point current = queue.poll();                int x = current.x;                int y = current.y;                int oneCount = current.oneCount;                // 对当前节点四个方向进行识别处理                for (int j = 0; j < 4; j++) {                    int xNew = x + dx[j];                    int yNew = y + dy[j];                    // 越界                    if (xNew < 0 || xNew >= m || yNew < 0 || yNew >= n) {                        continue;                    }                    // 搜索到目标节点则直接返回结果                    if (xNew == m - 1 && yNew == n - 1) {                        return minSteps;                    }                    // 穿越障碍次数已满                    if (grid[xNew][yNew] == 1 && oneCount >= k) {                        continue;                    }                    int oneCountNew = grid[xNew][yNew] == 1 ? oneCount + 1 : oneCount;                    // 四个方向节点是否被访问过（第三维度）                    if (visited[xNew][yNew][oneCountNew] == 1) {                        continue;                    } else {                        // 未被访问过且可以走的节点标记为访问过，对下一步节点确认状态非常重要                        // 将下一层级节点入队列标记为已访问，可以剪枝更多节点，节省计算耗时                        visited[xNew][yNew][oneCountNew] = 1;                    }                    queue.offer(new Point(xNew, yNew, oneCountNew));                }            }        }        // BFS没搜索到目标，返回-1        return -1;    }    private boolean validateInputParams(int k, int m, int n) {        return m > 40 || m < 1 || n > 40 || n < 1 || k < 1 || k > m * n;    }    class Point {        int x;        int y;        int oneCount;        public Point(int x, int y, int oneCount) {            this.x = x;            this.y = y;            this.oneCount = oneCount;        }    }
   

 

思路分析：

以后看到需要搜索求最短路的问题，直接用bfs！一开始写了个dfs加记忆化搜索还是TLE了！

当然这题的bfs有一定的坑点，导致我debug的时候一直很难察觉。比如说下面这个样例: [[0,1,0,0,0,1,0,0], [0,1,0,1,0,1,0,1], [0,0,0,1,0,0,1,0]] 一般我们bfs搜索，都是将已走过的路线进行标记避免重复遍历，但是这个样例就不行。因为如果按走过的路线进行标记，[0,0]->[1,0]->[1,1]->[1,2]，此时[1,2]已经被标记了。但是我们的正确路线并不是上面的那条，而是[0,0]->[1,0]->[2,0]->[2,1]->[2,2]->[1,2]->[0,2]… 当遍历到正确路线里的[2,2]时，就不会往上走了，因为[1,2]之前就被标记过了。因此我们记录已走的状态有3个：x, y, k. **vis[i][j][k]表示需要记录走到点[x,y]剩余k次消除数的步数。**如果当前状态和i,j,k一样并且步数大于vis[i][j][k]时就没必要将该结点加入到队列了。下面上代码：

class Solution {public:    struct node{        int x, y;        int k, cnt;    };    int vis[42][42][1602];	//用来存状态    int dx[4] = {1,-1,0,0};    int dy[4] = {0,0,1,-1};    int shortestPath(vector
   
    
     >& grid, int k) {        memset(vis,0x3f,sizeof(vis));	//初始化最大值        if(grid.size() == 0) return -1;        int n = grid.size(), m = grid[0].size();        node t; t.x = 0, t.y = 0, t.k = k, t.cnt = 0;        node tt;        queue
     
       q;        q.push(t);        while(!q.empty())        {            t = q.front();            q.pop();            if(t.x == n-1 && t.y == m-1 && t.k >= 0)            {                return t.cnt;            }            for(int i = 0;i < 4;i++)            {                int xx = dx[i]+t.x;                int yy = dy[i]+t.y;                if(xx >= 0 && xx < n && yy >= 0 && yy < m)                {                    if(grid[xx][yy] == 1 && t.k > 0)                    {                        if(vis[xx][yy][t.k-1] <= t.cnt+1) continue;                        vis[xx][yy][t.k-1] = t.cnt+1;                        tt.x = xx, tt.y = yy, tt.cnt = t.cnt+1, tt.k = t.k-1;                        q.push(tt);                    }                    else if(grid[xx][yy] == 0)                    {                        if(vis[xx][yy][t.k] <= t.cnt+1) continue;                        vis[xx][yy][t.k] = t.cnt+1;                        tt.x = xx, tt.y = yy, tt.cnt = t.cnt+1, tt.k = t.k;                        q.push(tt);                    }                }            }        }        return -1;    }};