1091. Shortest Path in Binary Matrix

1091。Shortest Path in Binary Matrix

Given an n x n binary matrix grid, return the length of the shortest clear path in the matrix. If there is no clear path, return -1.

A clear path in a binary matrix is a path from the top-left cell (i.e., (0, 0)) to the bottom-right cell (i.e., (n - 1, n - 1)) such that:

• All the visited cells of the path are 0.

• All the adjacent cells of the path are 8-directionally connected (i.e., they are different and they share an edge or a corner).

The length of a clear path is the number of visited cells of this path.

Example 1:

Input: grid = [[0,1],[1,0]]
Output: 2

Example 2:

Input: grid = [[0,0,0],[1,1,0],[1,1,0]]
Output: 4

My Solutions:

题目要求是只能在0上走，可以上下左右斜着走，问从左上到右下的最短路径，第一个格子也算一步。

public int[] ROWS    = {-1, -1, -1, 0, 0, 1, 1, 1};
public int[] COLUMNS = {-1,  0,  1, -1,1,-1, 0, 1};

public int shortestPathBinaryMatrix(int[][] grid) {
    int n = grid.length;
    if (grid[0][0] == 1 || grid[n - 1][n - 1] == 1) return -1; // 起点或终点不能走
    if (grid[0][0] == 0 && n == 1) return 1; // 只有一个格子且为0
    int pathLen = 1; //根据题意，第一个格子也要算

    Queue<int[]> q = new LinkedList<>(); // 用来存坐标
    q.offer(new int[]{0, 0});
    boolean[][] visited = new boolean[n][n]; // 用来标记走过的格子
    visited[0][0] = true;

    while (!q.isEmpty()) {
        int size = q.size();
        while (size > 0) { // 需要走遍q里每一个之前放进去的格子
            int[] curr = q.poll();
            int row = curr[0], col = curr[1];
            for (int i = 0; i < 8; i++) {
                int r = row + ROWS[i], c = col + COLUMNS[i];
                
                if (r < 0 || r >= n || c < 0 || c >= n || grid[r][c] != 0 || visited[r][c]) continue;

                if (r == n - 1 && c == n - 1) { //走到右下角目的地，直接返回
                    pathLen++;
                    return pathLen; 
                }
                q.offer(new int[]{r, c});
                visited[r][c] = true;
            }
            size--;
        }
        pathLen++; // while(size > 0)这个loop走完，需要+一步
    }
    return -1;
}