算法思想

深度搜索和广度搜索广泛应用于树和图中。

BFS一层一层的进行遍历，每层遍历都是以上一层的结果作为起点，遍历一个距离能访问到的所有节点，需要注意的是，遍历过的节点不能再次被遍历。

每一层遍历的节点都与根节点距离相同。设di表示第i个节点与根节点的距离，推导出一个结论：对于先遍历的节点i与后遍历的节点j，有di<dj。利用这个结论，可以求解最短路径等最优解问题：第一次遍历到的目的节点，其所经过的路径为最短路径。

使用BFS只能求解无权图的最短路径，无权图是指从一个节点到另一个节点的代价都记为1。

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

队列：用来存储每一轮遍历得到的节点

标记：对于遍历过的节点，应该将它标记，防止重复遍历。

题目

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

题目大意

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

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

路径途经的所有单元格都的值都是 0 。

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

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

解题思路

利用一个变量pathlength来计步，利用while(size-->0)来控制每一层的遍历，只有遍历完一层节点节点之后pathlength才进行加1，跳出该层循环的时候才会判断队列中有多少元素。第一次到达(m,n)坐标就返回，即对应最短路径。

代码实现

class Solution {    public int shortestPathBinaryMatrix(int[][] grid) {        //8个方向的BFS问题        if(grid==null||grid.length==0||grid[0].length==0){            return -1;        }        int[][] direction={  {-1,-1},{-1,0},{-1,1},{0,-1},{0,1},{1,-1},{1,0},{1,1}};        int m=grid.length,n=grid[0].length;        Queue
   
    
     > queue=new LinkedList<>();        queue.add(new Pair<>(0,0));        int pathlength=0;        while(!queue.isEmpty()){            int size=queue.size();            pathlength++;            //开始进入每一层相邻节点            while(size-->0){                Pair
     
       cur=queue.poll();                int cr=cur.getKey();                int cc=cur.getValue();                if(grid[cr][cc]==1){                    continue;                }                //到达终点                if(cr==m-1&&cc==n-1){                    return pathlength;                }                //标记走过的节点                grid[cr][cc]=1;                for(int[] d:direction){                    int nr=cr+d[0],nc=cc+d[1];                    if(nr<0||nr>=m||nc<0||nc>=n){                        continue;                    }                    queue.add(new Pair<>(nr,nc));                }            }        }        return -1;    }}

转载地址：http://lpwc.baihongyu.com/

你可能感兴趣的文章