專欄：50多種數(shù)據(jù)結構徹底征服

專欄：50多種經(jīng)典圖論算法全部掌握

3月28日王者榮耀官方賬號發(fā)文稱：由于服務器異常，部分玩家出現(xiàn)登錄異常、對局無法進入的問題，正在緊急處理中。經(jīng)近3個小時的搶修，官方于29日凌晨宣布修復完成，并補償玩家10張積分奪寶券及2張排位保護卡，有不少網(wǎng)友表示對這次的賠償比較滿意。

雖然這款游戲很火，也出來很多年了，但我從來都沒玩過，主要是不喜歡玩游戲，但我身邊也確實有不少人玩。王者榮耀總的用戶數(shù)量官方并沒有透露，但在2025年春節(jié)期間，受福利活動推動，日活躍用戶數(shù)攀升至1.5億，達到《英雄聯(lián)盟》巔峰日活的15倍，王者榮耀上線 9 年多至少為騰訊帶來101.1億美元（約為720.8億元）收入。

--------------下面是今天的算法題--------------

來看下今天的算法題，這題是LeetCode的第1293題：網(wǎng)格中的最短路徑，難度是困難。

給你一個 m * n 的網(wǎng)格，其中每個單元格不是 0（空）就是 1（障礙物）。每一步，您都可以在空白單元格中上、下、左、右移動。

如果您 最多 可以消除 k 個障礙物，請找出從左上角 (0, 0) 到右下角 (m-1, n-1) 的最短路徑，并返回通過該路徑所需的步數(shù)。如果找不到這樣的路徑，則返回 -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

問題分析

這題說的是找到一條從左上角到右下角的路徑，這條路徑所需要的步數(shù)最少，路徑中可能會有障礙物，但我們有 k 次機會消除障礙物。

如果只有障礙物而不能消除，這就是一道典型的BFS問題，我們只需要從起始點開始搜索，計算到終止點所需要的步數(shù)即可，但這里有消除障礙物的功能，所以還需要加個條件判斷。

假如沒有障礙物，從左上角到右下角只需要走 m+n-2 步即可，所以如果可消除的機會 k 大于等于 m+n-3（起始點和終止點沒有障礙物），我們一定可以把最短路徑上的所有障礙物全部消除。

當 k 不大于 m+n-3 的時候，我們可以通過BFS搜索來計算。因為這里是矩陣搜索，我們需要使用一個變量visited來記錄每個位置是否訪問過，以及到當前位置剩余可消除的數(shù)量。

如果當前位置沒有訪問過，或者剩余可消除的數(shù)量更大，我們就更新當前位置，然后把它添加到隊列中。剛開始的時候我們把每一個位置的值初始化為 -1 ，表示還沒有被訪問過。

關于矩陣的BFS訪問有一個模板，具體內(nèi)容大家可以看下中的第 9 章，掌握矩陣的BFS遍歷之后，我們只需要對模板稍微修改下即可。

JAVA：

public int shortestPath(int[][] grid, int k) { int m = grid.length; int n = grid[0].length; if (k >= m + n - 3)// 消除障礙物的數(shù)量比較大，可以找到一條最短路徑。       return m + n - 2;   k = Math.min(k, m + n - 3);   Queue

 q = new LinkedList<>();// 創(chuàng)建隊列   q.offer(newint[]{0, 0, k});// 添加起始位置 int ans = 0; // visited表示當前位置[i,j]是否訪問過，以及當前位置剩余可以消除的數(shù)量。 int[][] visited = newint[m][n]; for (int[] row : visited)       Arrays.fill(row, -1);// 初始化全部為 -1 ，表示所有位置都還沒有訪問過。 int[][] dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};// 方向數(shù)組   visited[0][0] = k;// 起始位置，剩余可消除的數(shù)量。 while (!q.isEmpty()) {       ans++;// 行走的步數(shù)       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];// 剩余可消除的數(shù)量。           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]是個障礙物，但沒有可消               // 除的數(shù)量了，所以要跳過。               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]沒有被訪問過，或者被訪問過，但剩余訪問的次數(shù)更多。               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)// 消除障礙物的數(shù)量比較大，可以找到一條最短路徑。             return m + n - 2;         k = min(k, m + n - 3);         queue

 > q;// 創(chuàng)建隊列         q.push({0, 0, k});// 添加起始位置         int ans = 0;         // visited表示當前位置[i,j]是否訪問過，以及當前位置剩余可以消除的數(shù)量。         vector

 > visited(m, vector

 (n, -1));         vector

 > dirs = {{-1, 0},                                     {1,  0},                                     {0,  -1},                                     {0,  1}};// 方向數(shù)組         visited[0][0] = k;// 起始位置，剩余可消除的數(shù)量。         while (!q.empty()) {             ans++;// 行走的步數(shù)             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];// 剩余可消除的數(shù)量。                 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]是個障礙物，但沒有可消                     // 除的數(shù)量了，所以要跳過。                     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]沒有被訪問過，或者被訪問過，但剩余訪問的次數(shù)更多。                     if (rest > visited[newX][newY]) {                         q.push({newX, newY, rest});                         visited[newX][newY] = rest;                     }                 }             }         }         return-1;     }

筆者簡介

博哥，真名：王一博，畢業(yè)十多年， 作者，專注于 數(shù)據(jù)結構和算法 的講解，在全球30多個算法網(wǎng)站中累計做題2000多道，在公眾號中寫算法題解800多題，對算法題有自己獨特的解題思路和解題技巧，喜歡的可以給個關注，也可以 下載我整理的1000多頁的PDF算法文檔 。