搜索题目：网格中的最短路径

题目

标题和出处

标题：网格中的最短路径

出处：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}m=grid.length
• n = grid[0].length \texttt{n} = \texttt{grid[0].length}n=grid[0].length
• 1 ≤ m, n ≤ 40 \texttt{1} \le \texttt{m, n} \le \texttt{40}1≤m, n≤40
• 1 ≤ k ≤ m × n \texttt{1} \le \texttt{k} \le \texttt{m} \times \texttt{n}1≤k≤m×n
• grid[i][j] \texttt{grid[i][j]}grid[i][j]是0 \texttt{0}0或1 \texttt{1}1
• grid[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 - 2m+n−2，除了起点和终点以外，路径上有m + n − 3 m + n - 3m+n−3个单元格。以下将从左上角到右下角的步数是m + n − 2 m + n - 2m+n−2的路径称为最少步数路径。

对于任意一条最少步数路径，路径上的障碍物个数不超过m + n − 3 m + n - 3m+n−3。如果k ≥ m + n − 3 k \ge m + n - 3k≥m+n−3，则一定可以将一条最少步数路径上的障碍物全部消除，通过最少步数路径从左上角到右下角，最少步数是m + n − 2 m + n - 2m+n−2。

当k < m + n − 3 k < m + n - 3k<m+n−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} + 1distance+1，继续访问该相邻状态。

• 如果相邻单元格是障碍物，且满足eliminations < k \textit{eliminations} < keliminations<k和相邻单元格与消除eliminations + 1 \textit{eliminations} + 1eliminations+1个障碍物对应的状态未访问，则将该相邻状态的最少步数更新为distance + 1 \textit{distance} + 1distance+1，继续访问该相邻状态。

遍历结束之后，如果未到达右下角，则不存在从左上角到右下角的路径，返回− 1 -1−1。

代码

classSolution{staticint[][]dirs={{-1,0},{1,0},{0,-1},{0,1}};publicintshortestPath(int[][]grid,intk){intm=grid.length,n=grid[0].length;if(k>=m+n-3){returnm+n-2;}int[][][]distances=newint[m][n][k+1];for(inti=0;i<m;i++){for(intj=0;j<n;j++){Arrays.fill(distances[i][j],Integer.MAX_VALUE);}}distances[0][0][0]=0;Queue<int[]>queue=newArrayDeque<int[]>();queue.offer(newint[]{0,0,0});while(!queue.isEmpty()){int[]state=queue.poll();introw=state[0],col=state[1],eliminations=state[2];intdistance=distances[row][col][eliminations];if(row==m-1&&col==n-1){returndistance;}for(int[]dir:dirs){intnewRow=row+dir[0],newCol=col+dir[1];if(newRow>=0&&newRow<m&&newCol>=0&&newCol<n){if(grid[newRow][newCol]==0){if(distances[newRow][newCol][eliminations]==Integer.MAX_VALUE){distances[newRow][newCol][eliminations]=distance+1;queue.offer(newint[]{newRow,newCol,eliminations});}}else{if(eliminations<k&&distances[newRow][newCol][eliminations+1]==Integer.MAX_VALUE){distances[newRow][newCol][eliminations+1]=distance+1;queue.offer(newint[]{newRow,newCol,eliminations+1});}}}}}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)的空间。