1091.二进制矩阵中的最短路径 - Java 基于BFS的层次遍历

原题地址：https://leetcode.cn/problems/shortest-path-in-binary-matrix/

题解

这道题的思路本质上就是BFS，从[0,0]开始进行BFS，搜素到[n-1,n-1]时返回当前广度即可，关键在于如何记录下广度

用cnt记录下当前广度的节点数，在BFS循环while(!queue.isEmpty())内套一个内层循环while(cnt)

当内层循环遍历完毕后，理所当然地，队列里剩下的节点全都是下一个广度的节点，所以在下一次循环时直接cnt=queue.size()即可

此外BFS要记得在更新queue时就维护skipped数组，而不是在取出节点时再维护，否则会重复遍历到相同节点

时间复杂度：O(N)

空间复杂度：O(N)

class Solution {
    public int shortestPathBinaryMatrix(int[][] grid) {
        if(grid[0][0]==1||grid[grid.length-1][grid[0].length-1]==1)return -1;
        int[][] skipped=new int[grid.length][grid[0].length];
        int floor=1,cnt=0;
        int[] element;
        int r,c,ir,ic;
        int[][] action={{-1,-1},{-1,0},{-1,1},{0,-1},{0,1},{1,-1},{1,0},{1,1}};
        
        for(r=0;r<grid.length;r++){
            for(c=0;c<grid[r].length;c++){
                if(grid[r][c]==1)skipped[r][c]=1;
            }
        }
        
        Queue<int[]> queue=new LinkedList<>();
        queue.add(new int[]{0,0});
        
       while(!queue.isEmpty()){
            cnt=queue.size();
            while(cnt>0){
                element=queue.remove();
                skipped[element[0]][element[1]]=1;
                if(element[0]==grid.length-1&&element[1]==grid[0].length-1){
                  return floor;
                }
                
                for(int i=0;i<action.length;i++){
                    ir=element[0]+action[i][0];
                    ic=element[1]+action[i][1];
                    if(ir>=0&&ir<grid.length&&ic>=0&&ic<grid[ir].length){
                        if(skipped[ir][ic]==0){
                            queue.add(new int[]{ir,ic});
                            skipped[ir][ic]=1;
                        }
                    }
                }
                
                cnt--;   
            }
            floor++;
        }

        return -1;
    }
}