1091. Shortest Path in Binary Matrix

 一刷 06/2022

Version #2 A* Algorithm[TODO]

Version #1 BFS

写了两个bug

一个是起点和终点不一定是0，需要特殊check

另一个是如果只有一个点，因为我是塞进que之前检查是不是终点，就会把（0，0）给忽略，也要做特殊检查 像答案是poll之后再检查就没有这个问题

Time O(MN)

Space O(MN)

Runtime: 16 ms, faster than 92.75% of Java online submissions for Shortest Path in Binary Matrix.

Memory Usage: 43.5 MB, less than 95.08% of Java online submissions for Shortest Path in Binary Matrix.

class Solution {

    private static int[] dx = new int[]{1, 1, 0, -1, -1, -1, 0, 1};

    private static int[] dy = new int[]{0, -1, -1, -1, 0, 1, 1, 1};

    public int shortestPathBinaryMatrix(int[][] grid) {

        if (grid == null || grid.length == 0 || grid[0] == null || grid[0].length == 0) {

            return 0;

        }

        if (grid[0][0] != 0 || grid[rows - 1][cols - 1] != 0) {

            return -1;

        }

        

        int rows = grid.length;

        int cols = grid[0].length;

        if (rows == 1 && cols == 1) {

            return 1;

        }

        Queue<int[]> que = new ArrayDeque<>();

        boolean[][] visited = new boolean[rows][cols];

        visited[0][0] = true;

        que.offer(new int[]{0, 0});

        int distances = 1;

        while (!que.isEmpty()) {

            int size = que.size();

            distances++;

            while (size-- > 0) {

                int[] curr = que.poll();

                for (int i = 0; i < 8; i++) {

                    int x = curr[1] + dx[i];

                    int y = curr[0] + dy[i];

                    if (x < 0 || x >= cols || y < 0 || y >= rows) {

                        continue;

                    }

                    

                    if (grid[y][x] != 0 || visited[y][x]) {

                        continue;

                    }

                    if (y == rows - 1 && x == cols - 1) {

                        return distances;

                    }

                    visited[y][x] = true;

                    que.offer(new int[]{y, x});

                }

            }

        }

        return -1;

    }

}