1091.Shortest Path in Binary Matrix

tags: Medium,Array,BFS,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

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

Jerry Wu1 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超像，好幾題類似題，但我還是因為邊界問題錯了兩次…
Marsgoat1 June, 2023

Reference

回到題目列表