1091. 二进制矩阵中的最短路径

左手的ㄟ右手 2024-04-01 19:11 64阅读 0赞

### 1091. 二进制矩阵中的最短路径 ###

给你一个 n x n 的二进制矩阵 grid 中，返回矩阵中最短 **畅通路径** 的长度。如果不存在这样的路径，返回 -1 。

二进制矩阵中的 畅通路径是一条从 **左上角** 单元格（即，(0, 0)）到 **右下角** 单元格（即，(n - 1, n - 1)）的路径，该路径同时满足下述要求：

*  路径途经的所有单元格都的值都是 0 。
 *  路径中所有相邻的单元格应当在 **8 个方向之一** 上连通（即，相邻两单元之间彼此不同且共享一条边或者一个角）。

**畅通路径的长度** 是该路径途经的单元格总数。

##### 示例 1： #####

![在这里插入图片描述][bc049a0a2fca415093b68a6ced04c7e6.png]

> 输入：grid = \[\[0,1\],\[1,0\]\]  
> 输出：2

##### 示例2： #####

![在这里插入图片描述][c1dcc973769b4a068059a834ae28b45f.png]

> 输入：grid = \[\[0,0,0\],\[1,1,0\],\[1,1,0\]\]  
> 输出：4

##### 示例3： #####

> 输入：grid = \[\[1,0,0\],\[1,1,0\],\[1,1,0\]\]  
> 输出：-1

##### 提示： #####

*  n == grid.length
 *  n == grid\[i\].length
 *  1 <= n <= 100
 *  grid\[i\]\[j\] 为 0 或 1

#### 思路：（BFS） ####

典型的BFS最短路径问题，用DFS也可以求解，但是容易超时。

##### 在二维矩阵中搜索，什么时候用BFS，什么时候用DFS？ #####

1.如果只是要找到某一个结果是否存在，那么 **DFS** 会更高效。因为DFS会首先把一种可能的情况尝试到底，才会回溯去尝试下一种情况，只要找到一种情况，就可以返回了。但是BFS必须所有可能的情况同时尝试，在找到一种满足条件的结果的同时，也尝试了很多不必要的路径；  
2.如果是要找所有可能结果中最短的，那么 **BFS** 回更高效。因为DFS是一种一种的尝试，在把所有可能情况尝试完之前，无法确定哪个是最短，所以DFS必须把所有情况都找一遍，才能确定最终答案（DFS的优化就是剪枝，不剪枝很容易超时）。而BFS从一开始就是尝试所有情况，所以只要找到第一个达到的那个点，那就是最短的路径，可以直接返回了，其他情况都可以省略了，所以这种情况下，BFS更高效。

##### BFS解法中的visited为什么可以全局使用？ #####

BFS是在尝试所有的可能路径，哪个最快到达终点，哪个就是最短。

那么每一条路径走过的路不同，visited（也就是这条路径上走过的点）也应该不同，那么为什么visited可以全局使用呢？  
因为我们要找的是最短路径，那么如果在此之前某个点已经在visited中，也就是说有其他路径在小于或等于当前步数的情况下，到达过这个点，证明到达这个点的最短路径已经被找到。那么显然这个点没必要再尝试了，因为即便去尝试了，最终的结果也不会是最短路径了，所以直接放弃这个点即可。

##### **在程序实现 BFS 时需要考虑以下问题：** #####

*  队列：用来存储每一轮遍历得到的节点；
 *  标记：对于遍历过的节点，应该将它标记，防止重复遍历

#### 代码：（Java） ####

import java.util.LinkedList;
    import java.util.Queue;
    
    public class bfs_bi_lesros {
        
    
    	public static void main(String[] args) {
        
    		// TODO 自动生成的方法存根
    		int [][]grid = {
        {
        0,0,0},{
        1,1,0},{
        1,1,0}};
    		System.out.println(shortestPathBinaryMatrix(grid));
    	}
    	public static int shortestPathBinaryMatrix(int[][] grid) {
        
    		
    		//过滤掉特殊情况
    		if(grid == null || grid.length ==0 || grid[0].length == 0) {
        
    			return -1;
    		}
    		//如果起点就阻塞肯定隔P
    		if(grid[0][0] == 1) {
        
    			return -1;
    		}
    		//可以走的8 个方向
    		int [][] dir= {
        {
        -1, -1}, {
        -1, 0}, {
        -1, 1}, {
        0, 1}, {
        1, 1}, {
        1, 0}, {
        1, -1}, {
        0, -1}};
    		int m = grid.length;//行
    		int n = grid[0].length;//列
    		
    		if(m != n)
    			return -1;
    		
    		//bfs的老套路 上队列
    		Queue<int[]> queue = new LinkedList<int[]>(); //LinkedList类实现了Queue接口，因此我们可以把LinkedList当成Queue来用
    		//将起点丢进去
    		queue.add(new int[]{
        0, 0});
    		
    		grid[0][0] = 1;//把起点设为阻塞,走过得直接阻塞
    		
    		int path = 1;//层数
    		
    		while(!queue.isEmpty()) {
        
    			int size = queue.size();//每一层的个数
    			while(size-- > 0) {
        
    				int [] cur = queue.poll();
    				int x = cur[0];
    				int y = cur[1];
    				
    				//如果等于终点则返回
    				if(x == m-1 && y == n-1) {
        
    					return path;
    				}
    				
    				//开始8个方向判断
    				for(int [] d : dir) {
        
    					int x1 = x + d[0];
    					int y1 = y + d[1];
    					
    					//过滤越界和阻塞的情况
    					if(x1 < 0 || x1 >= m || y1 < 0 || y1 >= m || grid[x1][y1] == 1) {
        
    						continue;
    					}
    					
    					//把在数组范围内，并且可以走的放入队列
    					queue.add(new int [] {
        x1, y1});
    					grid[x1][y1] = 1; //已走，设为阻塞
    				}
    			}
    			path++; //遍历完一层， 路径加1
    		}
    		
    		return -1;
        }
    }

##### 输出： #####

![在这里插入图片描述][80b30d5a5cbf4d60bcc6472bb3297008.png]

###### 注：仅供学习参考 ######

题目来源：[力扣][Link 1]

[bc049a0a2fca415093b68a6ced04c7e6.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/cde7ae45a97346ba817124ef457fa284.png
[c1dcc973769b4a068059a834ae28b45f.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/ba10dd7fcb0f4e988e56ee91e172c4e6.png
[80b30d5a5cbf4d60bcc6472bb3297008.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/d0aa686b271f4155a93ea38532c63839.png
[Link 1]: https://leetcode.cn/problems/shortest-path-in-binary-matrix/