专栏：50多种数据结构彻底征服
专栏：50多种经典图论算法全部掌握
3月28日王者荣耀官方账号发文称：由于服务器异常，部分玩家出现登录异常、对局无法进入的问题，正在紧急处理中。经近3个小时的抢修，官方于29日凌晨宣布修复完成，并补偿玩家10张积分夺宝券及2张排位保护卡，有不少网友表示对这次的赔偿比较满意。
虽然这款游戏很火，也出来很多年了，但我从来都没玩过，主要是不喜欢玩游戏，但我身边也确实有不少人玩。王者荣耀总的用户数量官方并没有透露，但在2025年春节期间，受福利活动推动，日活跃用户数攀升至1.5亿，达到《英雄联盟》巅峰日活的15倍，王者荣耀上线 9 年多至少为腾讯带来101.1亿美元（约为720.8亿元）收入。
--------------下面是今天的算法题--------------
来看下今天的算法题，这题是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 或 1
grid[0][0] == grid[m-1][n-1] == 0
问题分析
这题说的是找到一条从左上角到右下角的路径，这条路径所需要的步数最少，路径中可能会有障碍物，但我们有 k 次机会消除障碍物。
如果只有障碍物而不能消除，这就是一道典型的BFS问题，我们只需要从起始点开始搜索，计算到终止点所需要的步数即可，但这里有消除障碍物的功能，所以还需要加个条件判断。
假如没有障碍物，从左上角到右下角只需要走 m+n-2 步即可，所以如果可消除的机会 k 大于等于 m+n-3（起始点和终止点没有障碍物），我们一定可以把最短路径上的所有障碍物全部消除。
当 k 不大于 m+n-3 的时候，我们可以通过BFS搜索来计算。因为这里是矩阵搜索，我们需要使用一个变量visited来记录每个位置是否访问过，以及到当前位置剩余可消除的数量。
如果当前位置没有访问过，或者剩余可消除的数量更大，我们就更新当前位置，然后把它添加到队列中。刚开始的时候我们把每一个位置的值初始化为 -1 ，表示还没有被访问过。
关于矩阵的BFS访问有一个模板，具体内容大家可以看下中的第 9 章，掌握矩阵的BFS遍历之后，我们只需要对模板稍微修改下即可。
JAVA：
public int shortestPath(int[][] grid, int k) { int m = grid.length; int n = grid[0].length; if (k >= m + n - 3)// 消除障碍物的数量比较大，可以找到一条最短路径。 return m + n - 2; k = Math.min(k, m + n - 3); Queue
q = new LinkedList<>();// 创建队列 q.offer(newint[]{0, 0, k});// 添加起始位置 int ans = 0; // visited表示当前位置[i,j]是否访问过，以及当前位置剩余可以消除的数量。 int[][] visited = newint[m][n]; for (int[] row : visited) Arrays.fill(row, -1);// 初始化全部为 -1 ，表示所有位置都还没有访问过。 int[][] dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};// 方向数组 visited[0][0] = k;// 起始位置，剩余可消除的数量。 while (!q.isEmpty()) { ans++;// 行走的步数 int size = q.size(); for (int i = 0; i < size; i++) { int[] cur = q.poll();// 出队 int x = cur[0], y = cur[1]; int rest = cur[2];// 剩余可消除的数量。 if (grid[x][y] == 1)// 当前位置是 1 ，消除一个。 rest--; // 遍历当前位置[x,y]的上下左右四个方向。 for (int[] dir : dirs) { int newX = x + dir[0]; int newY = y + dir[1]; // 不能越界，或者当前位置[newX,newY]是个障碍物，但没有可消 // 除的数量了，所以要跳过。 if (newX < 0 || newX >= m || newY < 0 || newY >= n || (grid[newX][newY] == 1 && rest == 0)) continue; if (newX == m - 1 && newY == n - 1) return ans;// 到达目的地 // 当前位置[newX,newY]没有被访问过，或者被访问过，但剩余访问的次数更多。 if (rest > visited[newX][newY]) { q.offer(newint[]{newX, newY, rest}); visited[newX][newY] = rest; } } } } return -1; }
C++：
public: int shortestPath(vector
> &grid, int k) { int m = grid.size(); int n = grid[0].size(); if (k >= m + n - 3)// 消除障碍物的数量比较大，可以找到一条最短路径。 return m + n - 2; k = min(k, m + n - 3); queue
> q;// 创建队列 q.push({0, 0, k});// 添加起始位置 int ans = 0; // visited表示当前位置[i,j]是否访问过，以及当前位置剩余可以消除的数量。 vector
> visited(m, vector
(n, -1)); vector
> dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};// 方向数组 visited[0][0] = k;// 起始位置，剩余可消除的数量。 while (!q.empty()) { ans++;// 行走的步数 int size = q.size(); for (int i = 0; i < size; i++) { vector
cur = q.front(); q.pop();// 出队 int x = cur[0], y = cur[1]; int rest = cur[2];// 剩余可消除的数量。 if (grid[x][y] == 1)// 当前位置是 1 ，消除一个。 rest--; // 遍历当前位置[x,y]的上下左右四个方向。 for (auto &dir: dirs) { int newX = x + dir[0]; int newY = y + dir[1]; // 不能越界，或者当前位置[newX,newY]是个障碍物，但没有可消 // 除的数量了，所以要跳过。 if (newX < 0 || newX >= m || newY < 0 || newY >= n || (grid[newX][newY] == 1 && rest == 0)) continue; if (newX == m - 1 && newY == n - 1) return ans;// 到达目的地 // 当前位置[newX,newY]没有被访问过，或者被访问过，但剩余访问的次数更多。 if (rest > visited[newX][newY]) { q.push({newX, newY, rest}); visited[newX][newY] = rest; } } } } return-1; }
笔者简介
博哥，真名：王一博，毕业十多年， 作者，专注于 数据结构和算法 的讲解，在全球30多个算法网站中累计做题2000多道，在公众号中写算法题解800多题，对算法题有自己独特的解题思路和解题技巧，喜欢的可以给个关注，也可以 下载我整理的1000多页的PDF算法文档 。