# 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:**

![](https://assets.leetcode.com/uploads/2021/02/18/example1_1.png)

<pre><code><strong>Input: grid = [[0,1],[1,0]]
</strong><strong>Output: 2
</strong></code></pre>

**Example 2:**

![](https://assets.leetcode.com/uploads/2021/02/18/example2_1.png)

<pre><code><strong>Input: grid = [[0,0,0],[1,1,0],[1,1,0]]
</strong><strong>Output: 4
</strong></code></pre>

***My Solutions:***

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

```java
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;
}

```
