当前位置: 代码迷 >> 综合 >> leetcode 1293. 网格中的最短路径
  详细解决方案

leetcode 1293. 网格中的最短路径

热度:20   发布时间:2024-01-29 17:53:30.0

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

  • 题目描述
    • 概述
        • 题目类型扩展:
    • 方法一:visited访问标记数组二维 + 贪心 (推荐)
    • 方法二:visited访问标记数组三维扩展 (用于比较)

题目描述

给你一个 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<Node> 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搜索完成没找到结果,返回-1
return -1;

题目类型扩展:

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

方法一:visited访问标记数组二维 + 贪心 (推荐)

image.png

本题精髓在于对标记访问数组 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<Point> 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没搜索到目标,返回-1return -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次消除障碍物,就需要增加一个维度来记录同一个节点被访问的时候 已经使用消除障碍物的次数。:

image.png

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<Point> 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没搜索到目标,返回-1return -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;}}