1091. Shortest Path in Binary Matrix

A*

https://leetcode.com/problems/shortest-path-in-binary-matrix/discuss/313347/A*-search-in-Python

time: O(nlogn)

space: O(n)

之後回來寫

pure BFS

time: O(n^2)

space: O(n^2)

class Solution {
    // 8 directions
    private static final int[][] DIRECTIONS = {{0,1}, {1, 0}, {-1, 0}, {0,-1}, {1,1}, {-1,-1}, {-1,1}, {1,-1}};
    public int shortestPathBinaryMatrix(int[][] grid) {
        // 8 directions
        // contrait: == 0 & !vistited
        // when reach m - 1, n-1 return level
        // notice the edge case grid[0][0] == 1 || grid[n-1][n-1] == 1 should return -1
        
        if (grid == null || grid.length == 0) return -1;
        int n = grid.length;
        if(grid[0][0] == 1 || grid[n-1][n-1] == 1) return -1; // edge case
        
        boolean visited[][] = new boolean[n][n];
        Queue<int[]> queue = new LinkedList<>();
        queue.offer(new int[]{0, 0});
        visited[0][0] = true;
        
        int level = 0;
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int q = 0; q < size; q++) {
                int cell[] = queue.poll();
                if (cell[0] == n - 1 && cell[1] == n - 1) { // reach bottom-right
                    return level + 1;
                }
                for (int dir[] : DIRECTIONS) {
                    int x = cell[0] + dir[0];
                    int y = cell[1] + dir[1];
                    // All the visited cells of the path are 0
                    if (x >= 0 && x < n && y >= 0 && y < n && !visited[x][y] && grid[x][y] == 0) {
                        queue.offer(new int[]{x, y});
                        visited[x][y] = true;
                    }
                }
            }
            level++;
        }
        
        return -1;
    }
}