lintcode 1446 · 01矩阵走路问题 【两次BFS, VIP 中等 1也计算距离，但是不入队列】

题目链接，描述

https://www.lintcode.com/problem/1446

给定一个大小为 n*m 的 01 矩阵 grid ，1 是墙，0 是路，你现在可以把 grid 中的一个 1 变成 0，请问从左上角走到右下角是否有路可走？如果有路可走，最少要走多少步？1≤n≤1∗10^31≤m≤1∗10^3样例
样例 1：输入：a = [[0,1,0,0,0],[0,0,0,1,0],[1,1,0,1,0],[1,1,1,1,0]] 
输出：7
解释：将（0,1）处的 `1` 变成 `0`，最短路径如下：(0,0)->(0,1)->(0,2)->(0,3)->(0,4)->(1,4)->(2,4)->(3,4) 其他长度为 `7` 的方案还有很多，这里不一一列举。
样例 2：输入：a = [[0,1,1],[1,1,0],[1,1,0]]
输出：-1 
解释：不管把哪个 `1` 变成 `0`，都没有可行的路径。

思路、前置知识

 两次BFS两次BFS,从第一个位置开始得到距离数组arrS从最后一个位置开始得到距离数组arrE和常规BFS不同的时，遇到1也统计距离，但是该位置点不进入队列最后循环每个下标，检查2个数组的距离和是否都小于int最大值，结果就在这些下标里

参考代码

public class Solution {/*** @param grid: The gird* @return: Return the steps you need at least*/public int getBestRoad(int[][] grid) {//两次BFS,从第一个位置开始得到距离数组arrS// 从最后一个位置开始得到距离数组arrE//和常规BFS不同的时，遇到1也统计距离，但是该位置点不进入队列//最后循环每个下标，检查2个数组的距离和是否都小于int最大值，结果就在这些下标里if (grid == null || grid.length == 0 || grid[0].length == 0)return 0;int n = grid.length, m = grid[0].length;int len = n * m; //二维变一维int[] arrS = new int[len];int[] arrE = new int[len];Arrays.fill(arrS, Integer.MAX_VALUE);Arrays.fill(arrE, Integer.MAX_VALUE);bfs(0, 0, arrS, grid);  //从出发点开始统计距离bfs(n - 1, m - 1, arrE, grid); //从终点开始统计距离int ans =Integer.MAX_VALUE;for (int i = 0; i <n ; i++) {for (int j = 0; j <m ; j++) {int index = i*m+j;if(arrS[index] <Integer.MAX_VALUE && arrE[index] <Integer.MAX_VALUE){ans = Math.min(ans,arrS[index]+arrE[index]);}}}return ans < Integer.MAX_VALUE? ans:-1;}public static void bfs(int x, int y, int[] dis, int[][] arr) {Queue<Integer> q = new LinkedList<>();Set<Integer> visited = new HashSet<>();int[][] dirs = {{-1,0},{1,0},{0,-1},{0,1}}; //上下左右int n = arr.length,m= arr[0].length;q.add(x*m+y);visited.add(x*m+y);dis[x*m+y] = 0;int step =0;while (!q.isEmpty()){step++;int size = q.size();for (int i = 0; i <size ; i++) {int poll = q.poll();int x1 = poll/m;  //一维坐标转二维横坐标int y1 = poll-x1*m; //一维坐标转二纵横坐标for (int[] dir : dirs) {int x2=x1+dir[0],y2=y1+dir[1];if(x2>=0 && x2<n && y2>=0 && y2<m){int index2 = x2*m+y2;if(visited.contains(index2)) continue;dis[index2] = step; //不管是0还是1都要统计距离visited.add(index2);//只有空地才继续向外扩展if(arr[x2][y2] ==0){q.add(index2);}}}}}}
}