專欄：50多種數(shù)據(jù)結(jié)構(gòu)徹底征服
專欄：50多種經(jīng)典圖論算法全部掌握
3月28日王者榮耀官方賬號(hào)發(fā)文稱：由于服務(wù)器異常，部分玩家出現(xiàn)登錄異常、對(duì)局無法進(jìn)入的問題，正在緊急處理中。經(jīng)近3個(gè)小時(shí)的搶修，官方于29日凌晨宣布修復(fù)完成，并補(bǔ)償玩家10張積分奪寶券及2張排位保護(hù)卡，有不少網(wǎng)友表示對(duì)這次的賠償比較滿意。
雖然這款游戲很火，也出來很多年了，但我從來都沒玩過，主要是不喜歡玩游戲，但我身邊也確實(shí)有不少人玩。王者榮耀總的用戶數(shù)量官方并沒有透露，但在2025年春節(jié)期間，受福利活動(dòng)推動(dòng)，日活躍用戶數(shù)攀升至1.5億，達(dá)到《英雄聯(lián)盟》巔峰日活的15倍，王者榮耀上線 9 年多至少為騰訊帶來101.1億美元（約為720.8億元）收入。
--------------下面是今天的算法題--------------
來看下今天的算法題，這題是LeetCode的第1293題：網(wǎng)格中的最短路徑，難度是困難。
給你一個(gè) m * n 的網(wǎng)格，其中每個(gè)單元格不是 0（空）就是 1（障礙物）。每一步，您都可以在空白單元格中上、下、左、右移動(dòng)。
如果您 最多 可以消除 k 個(gè)障礙物，請(qǐng)找出從左上角 (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 解釋：我們至少需要消除兩個(gè)障礙才能找到這樣的路徑。
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ù)最少，路徑中可能會(huì)有障礙物，但我們有 k 次機(jī)會(huì)消除障礙物。
如果只有障礙物而不能消除，這就是一道典型的BFS問題，我們只需要從起始點(diǎn)開始搜索，計(jì)算到終止點(diǎn)所需要的步數(shù)即可，但這里有消除障礙物的功能，所以還需要加個(gè)條件判斷。
假如沒有障礙物，從左上角到右下角只需要走 m+n-2 步即可，所以如果可消除的機(jī)會(huì) k 大于等于 m+n-3（起始點(diǎn)和終止點(diǎn)沒有障礙物），我們一定可以把最短路徑上的所有障礙物全部消除。
當(dāng) k 不大于 m+n-3 的時(shí)候，我們可以通過BFS搜索來計(jì)算。因?yàn)檫@里是矩陣搜索，我們需要使用一個(gè)變量visited來記錄每個(gè)位置是否訪問過，以及到當(dāng)前位置剩余可消除的數(shù)量。
如果當(dāng)前位置沒有訪問過，或者剩余可消除的數(shù)量更大，我們就更新當(dāng)前位置，然后把它添加到隊(duì)列中。剛開始的時(shí)候我們把每一個(gè)位置的值初始化為 -1 ，表示還沒有被訪問過。
關(guān)于矩陣的BFS訪問有一個(gè)模板，具體內(nèi)容大家可以看下中的第 9 章，掌握矩陣的BFS遍歷之后，我們只需要對(duì)模板稍微修改下即可。
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)建隊(duì)列 q.offer(newint[]{0, 0, k});// 添加起始位置 int ans = 0; // visited表示當(dāng)前位置[i,j]是否訪問過，以及當(dāng)前位置剩余可以消除的數(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();// 出隊(duì) int x = cur[0], y = cur[1]; int rest = cur[2];// 剩余可消除的數(shù)量。 if (grid[x][y] == 1)// 當(dāng)前位置是 1 ，消除一個(gè)。 rest--; // 遍歷當(dāng)前位置[x,y]的上下左右四個(gè)方向。 for (int[] dir : dirs) { int newX = x + dir[0]; int newY = y + dir[1]; // 不能越界，或者當(dāng)前位置[newX,newY]是個(gè)障礙物，但沒有可消 // 除的數(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;// 到達(dá)目的地 // 當(dāng)前位置[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)建隊(duì)列 q.push({0, 0, k});// 添加起始位置 int ans = 0; // visited表示當(dāng)前位置[i,j]是否訪問過，以及當(dāng)前位置剩余可以消除的數(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();// 出隊(duì) int x = cur[0], y = cur[1]; int rest = cur[2];// 剩余可消除的數(shù)量。 if (grid[x][y] == 1)// 當(dāng)前位置是 1 ，消除一個(gè)。 rest--; // 遍歷當(dāng)前位置[x,y]的上下左右四個(gè)方向。 for (auto &dir: dirs) { int newX = x + dir[0]; int newY = y + dir[1]; // 不能越界，或者當(dāng)前位置[newX,newY]是個(gè)障礙物，但沒有可消 // 除的數(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;// 到達(dá)目的地 // 當(dāng)前位置[newX,newY]沒有被訪問過，或者被訪問過，但剩余訪問的次數(shù)更多。 if (rest > visited[newX][newY]) { q.push({newX, newY, rest}); visited[newX][newY] = rest; } } } } return-1; }
筆者簡介
博哥，真名：王一博，畢業(yè)十多年， 作者，專注于 數(shù)據(jù)結(jié)構(gòu)和算法 的講解，在全球30多個(gè)算法網(wǎng)站中累計(jì)做題2000多道，在公眾號(hào)中寫算法題解800多題，對(duì)算法題有自己獨(dú)特的解題思路和解題技巧，喜歡的可以給個(gè)關(guān)注，也可以 下載我整理的1000多頁的PDF算法文檔 。
熱門跟貼