题目大意：
网格中的最短路径
给你一个 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 or 1
- grid[0][0] == grid[m-1][n-1] == 0
如果想查看本题目是哪家公司的面试题，请参考以下免费链接： https://leetcode.jp/problemdetail.php?id=1293
解题思路分析：
leetcode中有很多01格子求最短路径的问题。之前文章讲过多次，这类求最短路径题型优先考虑bfs广度优先搜索的算法，本题也不例外。不过这道题的特殊之处在于，障碍物是可以被忽略的，忽略障碍物的最大次数不能超过k次。因此我们可以将所有搜索路径看成2种，一种路径是完全由0组成（普通路径），另一种路径中至少包含一个1（穿越路径），也就是穿越过障碍物的路径。
在普通的bfs中，为了避免走重复的路径，我们一般采用visited数组来记录下走过的格子，当路径遇到一个已走过的格子时，便不能再通过该点。但本题略有不同，上面说过，本题存在两种路径，因此visited数组中的状态应该包含3中状态：
- 0：该位置没有走过
- 1：该位置被普通路径走过
- 2：该路径被穿越路径走过
对于以上三种状态，
- 当前格子为非障碍物时，普通路径可以走访问状态为0的格子，走过后，访问状态更新为1
- 当前格子为非障碍物时，穿越路径可以走访问状态为0的格子，走过后，访问状态更新为2
- 当前格子为非障碍物时，普通路径可以走访问状态为2的格子，走过后，访问状态更新为1
- 当前格子为障碍物时，如果还保有穿越次数，并且该格子的访问状态为0时，所有路径可以通过此处，通过后，该路径变为穿越路径，并且当前格子访问状态更新为1（更新为2也无所谓）
对于以上4种走法，1，2，4很好解释，即没走过的格子肯定可以走。个人认为只有第三点不太容易理解，为什么穿越路径走过的非障碍物格子，普通路径还可以再走一遍？另外，为什么普通路径走过的格子，穿越路径不能再次通过呢？这要从最优解的角度来考虑。
首先考虑没有障碍物的情况下，从左上走到右下的最优解一定是以下操作：即每次只能向右或向下移动。反过来说，如果一条路径出现了向左或者向上的移动时一定不是最优解。接下来考虑存在障碍物的情况，如果想找到最优解，在不穿越的前提下，我们可能不得不做出向上或向左的移动，而穿墙操作则是相当于走近路，避免了绕墙运动而增加步数。但我们不能忽略的是，当我们有选择向下或者向右移动的时候，此时向上或者向左穿墙在全局路线上来看可能是不必要的操作，这不必要的操作的最大问题在于，该路线有可能提前使用完穿墙次数而导致接下来无路可走，那么他所走过的路线实际上是无效的，如果我们将这些无效的路径也计做已访问状态的话，会影响到我们正常线路的进行。这里回答了上面第一个问题。
对于第二个问题，为什么普通路径走过的格子，穿越路径不能再次通过？按照第一个问题的解释，我们知道，穿越障碍物实际上是为了走近路，也就是说有效的穿越路线一定是等于或者优于普通路线的，因此穿越路线无需再次通过普通路线走过的格子。
想通了以上的问题之后，题目就会迎刃而解，惯例先建立一个Queue和一个visited数组，起始时，起点[0,0]的访问状态为1，bfs使用的Queue中存放起点坐标，以及当前所剩的穿越次数。在bfs时，判断当前路径是否为穿越路径的方法是看其所剩的穿越次数是否与题目给出的k值相同即可。
实现代码：
public int shortestPath(int[][] grid, int k) {
// 访问数组。0：未访问。1：普通路径访问过。2：穿越路径访问过
int[][] visited = new int[grid.length][grid[0].length];
// bfs的四个方向
int[][] directions = new int[][]{{0,1},{0,-1},{1,0},{-1,0}};
Queue<int[]> q = new LinkedList<>();
// 将起点以及k放入queue
q.offer(new int[]{0,0,k});
// 返回结果
int res=0;
while(q.size()>0){
int size=q.size();
while(size>0){
size--;
int[] n = q.poll();
// 当前点是终点时，返回
if(n[0]==grid.length-1&&n[1]==grid[0].length-1){
return res;
}
// 从当前点向四个方向走一格
for(int[] d : directions){
// 下一格的坐标
int r=n[0]+d[0],c=n[1]+d[1];
// 格子在地图范围内
if(r>=0&&r<grid.length&&c>=0&&c<grid[0].length){
// 下一格不是障碍物
if(grid[r][c]==0){
// 访问状态为0时，普通路线与穿越路线均可走
if(visited[r][c]==0){
// 更新访问状态
visited[r][c]=(n[2]==k?1:2);
// 将下一格加入Queue，k值不变
q.offer(new int[]{r,c,n[2]});
}else if(visited[r][c]==2&&n[2]==k){
// 普通路径可以通过穿越路径走过的点
visited[r][c]=1;
// 将下一格加入Queue，k值不变
q.offer(new int[]{r,c,n[2]});
}
}else if(n[2]>0){ // 下一格是障碍物并且穿越次数大于0
if(visited[r][c]==0){ // 未访问过该点
// 更新访问状态
visited[r][c]=2;
// 将下一格加入Queue，k值减一
q.offer(new int[]{r,c,n[2]-1});
}
}
}
}
}
res++;
}
return -1;
} 本题解法执行时间为4ms。
Runtime: 4 ms, faster than 96.22% of Java online submissions for Shortest Path in a Grid with Obstacles Elimination.
Memory Usage: 40.5 MB, less than 100.00% of Java online submissions for Shortest Path in a Grid with Obstacles Elimination.
解法二：dfs深度优先搜索
其实本题同样可以采用dfs，时间复杂度与bfs相同，但由于dfs中不需要使用Queue，因此执行效率略优于bfs。实现的核心逻辑与bfs完全相同，以下代码仅供参考。
int[][] dir = new int[][]{{1,0},{0,1},{-1,0},{0,-1}};
int[][] visited;
int mK;
public int shortestPath(int[][] grid, int k) {
mK=k;
visited=new int[grid.length][grid[0].length];
return dfs(grid,0,0,k);
}
int dfs(int[][] grid,int row, int col, int k){
if(row==grid.length-1&&col==grid[0].length-1) return 0;
int res=Integer.MAX_VALUE;
for(int[]d : dir){
int r=row+d[0],c=col+d[1];
if(r>=0&&r<grid.length&&c>=0&&c<grid[0].length){
if(grid[r][c]==0){
if(visited[r][c]==0){
visited[r][c]= (k==mK ? 1 : 2);
int step=dfs(grid,r,c,k);
if(step!=-1){
res=Math.min(res, 1+step);
}
}else if(visited[r][c]==2&&k==mK){
visited[r][c]=1;
int step=dfs(grid,r,c,k);
if(step!=-1){
res=Math.min(res, 1+step);
}
}
}else if(k>0&&visited[r][c]==0){
visited[r][c]=2;
int step=dfs(grid,r,c,k-1);
if(step!=-1){
res=Math.min(res, 1+step);
}
}
}
}
return res==Integer.MAX_VALUE?-1:res;
} dfs解法执行时间为1ms。
Runtime: 1 ms, faster than 99.43% of Java online submissions for Shortest Path in a Grid with Obstacles Elimination.
Memory Usage: 36.6 MB, less than 100.00% of Java online submissions for Shortest Path in a Grid with Obstacles Elimination.
本网站文章均为原创内容，并可随意转载，但请标明本文链接如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: http://leetcode.jp/leetcode-1293-shortest-path-in-a-grid-with-obstacles-elimination-解题思路分析/