LeetCode(1091) -- Shortest Path in Binary Matrix

Problem

In an N by N square grid, each cell is either empty (0) or blocked (1).

A clear path from top-left to bottom-right has length k if and only if it is composed of cells C_1, C_2, …, C_k such that:

Adjacent cells C_i and C_{i+1} are connected 8-directionally (ie., they are different and share an edge or corner) C_1 is at location (0, 0) (ie. has value grid[0][0]) C_k is at location (N-1, N-1) (ie. has value grid[N-1][N-1]) If C_i is located at (r, c), then grid[r][c] is empty (ie. grid[r][c] == 0). Return the length of the shortest such clear path from top-left to bottom-right. If such a path does not exist, return -1.

My Solution

借鉴了双边BFS的方法，startSet和endSet，以及reverse。把左上那部分访问过的标记为1，右下部分访问过的标记为2。这样就能区别是否遇到的是自己访问过的还是对面访问过的。

class Solution {
    int shortest = 2;
    int n;
    int[][] visited;
    public int shortestPathBinaryMatrix(int[][] grid) {
        n = grid.length;
        visited = new int[n][n];
        if (grid[0][0] != 0 || grid[n - 1][n - 1] != 0) {
            return -1;
        }
        if (n == 1) {
            return 1;
        }
        Set<Integer> start = new HashSet<>();
        Set<Integer> end = new HashSet<>();
        start.add(0);
        visited[0][0] = 1;
        visited[n - 1][n - 1] = 2;
        end.add(n * n - 1);
        bfs(start, end, false, grid);
        return shortest;
    }
    
    private void bfs(Set<Integer> start, Set<Integer> end, boolean reverse, int[][] grid) {
        System.out.println(shortest);
        if (start.size() == 0) {
            shortest = -1;
            return;
        }
        if (start.size() > end.size()) {
            bfs(end, start, !reverse, grid);
            return;
        }
        Set<Integer> temp = new HashSet<>();
        boolean finish = false;
        for (Integer s : start) {
            int i = s / n;
            int j = s % n;
            for (int next_i = i - 1; next_i <= i + 1; next_i++) {
                for (int next_j = j - 1; next_j <= j + 1; next_j++) {
                    if (next_i < 0 || next_i >= n || next_j < 0 || next_j >= n || grid[next_i][next_j] != 0) {
                        continue;
                    }
                    if (!reverse && visited[next_i][next_j] == 1 || reverse && visited[next_i][next_j] == 2) {
                        continue;
                    }
                    visited[next_i][next_j] = reverse ? 2 : 1;
                    int next = next_i * n + next_j;
                    if (end.contains(next)) {
                        finish = true;
                    } else {
                        temp.add(next);
                    }
                }
            }
        }
        if (!finish) {
            shortest++;
            bfs(temp, end, reverse, grid);
        }
    }
}

The Best Solution

class Solution {
    public int shortestPathBinaryMatrix(int[][] grid) {
        int N = grid.length;
        if (grid[0][0] != 0 || grid[N-1][N-1] != 0) {
            return -1;
        }
        int len = 0;
        Queue<int[]> q = new LinkedList<>();
        q.add(new int[] {0, 0});
        while (!q.isEmpty()) {
            int size = q.size();
            len++;
            for (int i = 0; i < size; i++) {
                int[] n = q.poll();
                int r = n[0], c = n[1];
                if (r == N-1 && c == N - 1) {
                    return len;
                }
                for (int x = -1; x <= 1; x++) {
                    for (int y = -1; y <= 1; y++) {
                        int nr = r + x;
                        int nc = c + y;
                        if (nr >= 0 && nc >= 0 && nr < N && nc < N && grid[nr][nc] == 0) {
                            grid[nr][nc] = 2;
                            q.add(new int[] {nr, nc});
                        }
                    }
                }
            }
        }
        return -1;
    }
}