最近王者荣耀崩了，腾讯给每个账号都补偿了啥？

专栏：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算法文档 。