博客

class Solution {
    public static int shortestPathBinaryMatrix(int[][] grid) {
        int [][] dir = {{-1,-1},{-1,0},{-1,1},{0,-1},{0,1},{1,-1},{1,0},{1,1}};
        int minLength[][] = new int[grid.length][grid.length];
        Queue<int[]> queue = new LinkedList<>();
        int beginX = 0,beginY = 0;
        int endX = grid.length-1,endY = grid[0].length-1;
        int [] beginIndex = {beginX,beginY};
        queue.offer(beginIndex);
        for (int i = 0; i < minLength.length; i++) {
            for (int j = 0; j < minLength.length; j++) {
                minLength[i][j] = -1;
            }
        }
        minLength[beginX][beginY] = 1;

        while (!queue.isEmpty()){
            int [] headIndex = queue.poll();
            int x = headIndex[0],y=headIndex[1];
            if((x == endX && y ==endY) || (x==0 && y==0 && grid[x][y] == 1)){
                break;
            }
            for (int i = 0; i < dir.length; i++) {
                int dx = x+dir[i][0],dy = y+dir[i][1];
                int [] nextIndex = {dx,dy};
                if(dx>=0 && dy>=0 && dx<grid.length && dy<grid.length && minLength[dx][dy]==-1 && grid[dx][dy]==0){
                    queue.offer(nextIndex);
                    minLength[dx][dy] = minLength[x][y] + 1;
                }
            }
        }

        return minLength[endX][endY];
    }
}