1091.Shortest Path in Binary Matrix
===

###### tags: `Medium`,`Array`,`BFS`,`Matrix`

[1091. Shortest Path in Binary Matrix](https://leetcode.com/problems/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

**Example 3:**

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

**Constraints**:

* `n` == `grid.length`
* `n` == `grid[i].length`
* 1 <= `n` <= 100
* `grid[i][j]` is `0` or `1`

### 解答
#### C++
BFS

class Solution {
public:
    const int CLEAR = 0;
    int shortestPathBinaryMatrix(vector<vector<int>>& grid) {
        ios_base::sync_with_stdio(0), cin.tie(0);
        if (grid[0][0] == 1 - CLEAR) {
            return -1;
        }
        int n = grid.size();
        vector<pair<int, int>> delta = {
            {-1, -1}, {-1, 0}, {-1, 1},
            {0, -1}, {0, 1},
            {1, -1}, {1, 0}, {1, 1}
        };
        queue<pair<int, int>> frontier;
        frontier.push({0, 0});
        grid[0][0] = 1 - CLEAR;
        
        while (not frontier.empty()) {
            const auto [r, c] = frontier.front();
            if (r == n - 1 and c == n - 1) {
                return grid[r][c];
            }
            for (const auto [dr, dc] : delta) {
                if (r + dr < 0 or r + dr >= n or \
                    c + dc < 0 or c + dc >= n or \
                    grid[r + dr][c + dc] != CLEAR) {
                        continue;
                }
                frontier.push({r + dr, c + dc});
                grid[r + dr][c + dc] = grid[r][c] + 1;
            }
            frontier.pop();
        }
        return -1;
    }
};

> [name=Jerry Wu][time=1 June, 2023]

#### Javascript

function shortestPathBinaryMatrix(grid) {
  const isInBounds = (x, y, xLength, yLength) => x < xLength && x >= 0 && y < yLength && y >= 0;
  const n = grid.length;
  const m = grid[0].length;

  if (grid[0][0] === 1 || grid[n - 1][m - 1] === 1) return -1;

  const queue = [[0, 0, 1]];
  while (queue.length) {
    const [x, y, step] = queue.shift();
    if (grid[x][y] === 1) continue;

    if (x === n - 1 && y === m - 1) return step;

    const neighbors = [
      [x, y - 1],
      [x, y + 1],
      [x + 1, y],
      [x - 1, y],
      [x + 1, y + 1],
      [x + 1, y - 1],
      [x - 1, y + 1],
      [x - 1, y - 1],
    ];

    for (const [nx, ny] of neighbors) {
      if (isInBounds(nx, ny, n, m) && grid[nx][ny] === 0) {
        queue.push([nx, ny, step + 1]);
        grid[x][y] = 1;
      }
    }
  }

  return -1;
}

> 跟1926超像，好幾題類似題，但我還是因為邊界問題錯了兩次...
> [name=Marsgoat][time=1 June, 2023]

### Reference

[回到題目列表](https://hackmd.io/@Marsgoat/leetcode_every_day)