文章目录题目标题和出处难度题目描述要求示例数据范围解法思路和算法代码复杂度分析题目标题和出处标题网格中的最短路径出处1293. 网格中的最短路径难度6 级题目描述要求给定一个m × n \texttt{m} \times \texttt{n}m×n的矩阵grid \texttt{grid}grid其中每个单元格是0 \texttt{0}0空白或1 \texttt{1}1障碍物。每一步可以在空白单元格中上、下、左、右移动。如果最多可以消除k \texttt{k}k个障碍物返回从左上角(0, 0) \texttt{(0, 0)}(0, 0)到右下角(m − 1, n − 1) \texttt{(m} - \texttt{1, n} - \texttt{1)}(m−1, n−1)的最少步数。如果找不到这样的路径则返回-1 \texttt{-1}-1。示例示例 1输入grid [[0,0,0],[1,1,0],[0,0,0],[0,1,1],[0,0,0]], k 1 \texttt{grid [[0,0,0],[1,1,0],[0,0,0],[0,1,1],[0,0,0]], k 1}grid [[0,0,0],[1,1,0],[0,0,0],[0,1,1],[0,0,0]], k 1输出6 \texttt{6}6解释不消除任何障碍的最短路径是10 \texttt{10}10。消除位置(3,2) \texttt{(3,2)}(3,2)处的障碍后最短路径是6 \texttt{6}6。该路径是(0,0) → (0,1) → (0,2) → (1,2) → (2,2) → (3,2) → (4,2) \texttt{(0,0)} \rightarrow \texttt{(0,1)} \rightarrow \texttt{(0,2)} \rightarrow \texttt{(1,2)} \rightarrow \texttt{(2,2)} \rightarrow \texttt{(3,2)} \rightarrow \texttt{(4,2)}(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 \texttt{grid [[0,1,1],[1,1,1],[1,0,0]], k 1}grid [[0,1,1],[1,1,1],[1,0,0]], k 1输出-1 \texttt{-1}-1解释至少需要消除两个障碍才能到右下角。数据范围m grid.length \texttt{m} \texttt{grid.length}mgrid.lengthn grid[0].length \texttt{n} \texttt{grid[0].length}ngrid[0].length1 ≤ m, n ≤ 40 \texttt{1} \le \texttt{m, n} \le \texttt{40}1≤m, n≤401 ≤ k ≤ m × n \texttt{1} \le \texttt{k} \le \texttt{m} \times \texttt{n}1≤k≤m×ngrid[i][j] \texttt{grid[i][j]}grid[i][j]是0 \texttt{0}0或1 \texttt{1}1grid[0][0] grid[m − 1][n − 1] 0 \texttt{grid[0][0]} \texttt{grid[m} - \texttt{1][n} - \texttt{1]} \texttt{0}grid[0][0]grid[m−1][n−1]0解法思路和算法矩阵的行数和列数分别是m mm和n nn。如果矩阵中没有障碍物则从左上角到右下角的最少步数是m n − 2 m n - 2mn−2除了起点和终点以外路径上有m n − 3 m n - 3mn−3个单元格。以下将从左上角到右下角的步数是m n − 2 m n - 2mn−2的路径称为最少步数路径。对于任意一条最少步数路径路径上的障碍物个数不超过m n − 3 m n - 3mn−3。如果k ≥ m n − 3 k \ge m n - 3k≥mn−3则一定可以将一条最少步数路径上的障碍物全部消除通过最少步数路径从左上角到右下角最少步数是m n − 2 m n - 2mn−2。当k m n − 3 k m n - 3kmn−3时需要使用广度优先搜索计算最少步数。由于最多可以消除k kk个障碍物因此广度优先搜索的状态包括单元格所在的行下标、列下标和已经消除的障碍物个数。初始时位于矩阵的左上角消除零个障碍物最少步数是0 00将其余状态的最少步数初始化为无穷大。对于每个状态得到当前状态的行下标、列下标和已经消除的障碍物个数记已经消除的障碍物个数是eliminations \textit{eliminations}eliminations记当前状态的最少步数是distance \textit{distance}distance。如果当前状态已经到达右下角则返回distance \textit{distance}distance。如果当前状态尚未到达右下角则对于四个方向上的每个相邻单元格执行如下操作。如果相邻单元格是空白且相邻单元格与消除eliminations \textit{eliminations}eliminations个障碍物对应的状态未访问则将该相邻状态的最少步数更新为distance 1 \textit{distance} 1distance1继续访问该相邻状态。如果相邻单元格是障碍物且满足eliminations k \textit{eliminations} keliminationsk和相邻单元格与消除eliminations 1 \textit{eliminations} 1eliminations1个障碍物对应的状态未访问则将该相邻状态的最少步数更新为distance 1 \textit{distance} 1distance1继续访问该相邻状态。遍历结束之后如果未到达右下角则不存在从左上角到右下角的路径返回− 1 -1−1。代码classSolution{staticint[][]dirs{{-1,0},{1,0},{0,-1},{0,1}};publicintshortestPath(int[][]grid,intk){intmgrid.length,ngrid[0].length;if(kmn-3){returnmn-2;}int[][][]distancesnewint[m][n][k1];for(inti0;im;i){for(intj0;jn;j){Arrays.fill(distances[i][j],Integer.MAX_VALUE);}}distances[0][0][0]0;Queueint[]queuenewArrayDequeint[]();queue.offer(newint[]{0,0,0});while(!queue.isEmpty()){int[]statequeue.poll();introwstate[0],colstate[1],eliminationsstate[2];intdistancedistances[row][col][eliminations];if(rowm-1coln-1){returndistance;}for(int[]dir:dirs){intnewRowrowdir[0],newColcoldir[1];if(newRow0newRowmnewCol0newColn){if(grid[newRow][newCol]0){if(distances[newRow][newCol][eliminations]Integer.MAX_VALUE){distances[newRow][newCol][eliminations]distance1;queue.offer(newint[]{newRow,newCol,eliminations});}}else{if(eliminationskdistances[newRow][newCol][eliminations1]Integer.MAX_VALUE){distances[newRow][newCol][eliminations1]distance1;queue.offer(newint[]{newRow,newCol,eliminations1});}}}}}return-1;}}复杂度分析时间复杂度O ( m n k ) O(mnk)O(mnk)其中m mm和n nn分别是矩阵的行数和列数k kk是最多可以消除的障碍物个数。广度优先搜索的状态数是O ( m n k ) O(mnk)O(mnk)每个状态最多访问一次。空间复杂度O ( m n k ) O(mnk)O(mnk)其中m mm和n nn分别是矩阵的行数和列数k kk是最多可以消除的障碍物个数。记录每个状态的最少步数的三维数组和队列需要O ( m n k ) O(mnk)O(mnk)的空间。