1091.二进制矩阵中的最短路径

链接：1091.二进制矩阵中的最短路径
难度：Medium
标签：广度优先搜索、数组、矩阵
简介：给你一个 n x n 的二进制矩阵 grid 中，返回矩阵中最短 畅通路径 的长度。如果不存在这样的路径，返回 -1 。

题解 1 - typescript

• 编辑时间：2021-07-25
• 执行用时：92ms
• 内存消耗：43.9MB
• 编程语言：typescript
• 解法介绍：bfs。

function movingCount(m: number, n: number, k: number): number {
  const queue: [number, number, number][] = [[0, 0, 1]];
  const format = (row: number, col: number) => `${row}::${col}`;
  const set = new Set(queue.map(([row, col]) => format(row, col)));
  let ans = 1;
  const add = (row: number, col: number, count: number) => {
    const str = format(row, col);
    if (set.has(str)) return;
    set.add(str);
    const data: [number, number, number] = [row, col, count];
    let num = 0;
    while (row) {
      num += row % 10;
      row = ~~(row / 10);
    }
    while (col) {
      num += col % 10;
      col = ~~(col / 10);
    }
    if (num > k) return;
    queue.push(data);
    ans++;
  };
  while (queue.length) {
    const [row, col, count] = queue.shift()!;
    if (row) if (row > 0) add(row - 1, col, count + 1);
    if (col > 0) add(row, col - 1, count + 1);
    if (row < n - 1) add(row + 1, col, count + 1);
    if (col < m - 1) add(row, col + 1, count + 1);
  }
  return ans;
}

题解 2 - cpp

• 编辑时间：2023-05-26
• 执行用时：68ms
• 内存消耗：19.2MB
• 编程语言：cpp
• 解法介绍：bfs。

#define X first
#define Y second
#define pii pair<int, int>
vector<vector<int>> dirs2 = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}, {1, 1}, {1, -1}, {-1, 1}, {-1, -1}};
class Solution {
    public:
    int shortestPathBinaryMatrix(vector<vector<int>> &grid) {
        if (grid[0][0] == 1) return -1;
        queue<pii> q;
        q.push(make_pair(0, 0));
        int n = grid.size(), size = 1, step = 1;
        vector<vector<bool>> used(n, vector<bool>(n, false));
        while (q.size()) {
            auto cur = q.front();
            q.pop();
            if (cur.X == n - 1 && cur.Y == n - 1) return step;
            for (auto &dir : dirs2) {
                int nx = cur.X + dir[0], ny = cur.Y + dir[1];
                if (nx >= 0 && nx < n && ny >= 0 && ny < n && grid[nx][ny] == 0 && !used[nx][ny]) {
                    used[nx][ny] = true;
                    q.push(make_pair(nx, ny));
                }
            }
            if (--size == 0) {
                size = q.size();
                step += 1;
            }
        }
        return -1;
    }
};

题解 3 - python

• 编辑时间：2023-05-26
• 执行用时：256ms
• 内存消耗：16.6MB
• 编程语言：python
• 解法介绍：同上。

dirs2 = [(0, 1), (0, -1), (1, 0), (-1, 0), (1, 1), (1, -1), (-1, 1), (-1, -1)]
    class Solution:
        def shortestPathBinaryMatrix(self, grid: List[List[int]]) -> int:
            if grid[0][0] == 1:
                return -1
            q = deque()
            q.append((0, 0))
            n = len(grid)
            step = size = 1
            used = [[False for _ in range(n)] for _ in range(n)]
            while len(q):
                (x, y) = q.popleft()
                if x == n - 1 and y == n - 1:
                    return step
                for dir in dirs2:
                    nx = x + dir[0]
                    ny = y + dir[1]
                    if nx >= 0 and nx < n and ny >= 0 and ny < n and grid[nx][ny] == 0 and not used[nx][ny]:
                        used[nx][ny] = True
                        q.append((nx, ny))
                size -= 1
                if size == 0:
                    size = len(q)
                    step += 1
            return -1

题解 4 - rust

• 编辑时间：2023-05-26
• 执行用时：16ms
• 内存消耗：2.1MB
• 编程语言：rust
• 解法介绍：同上。

pub const dirs2: [[i32; 2]; 8] = [[0, 1], [0, -1], [1, 0], [-1, 0], [1, 1], [1, -1], [-1, 1], [-1, -1]];
impl Solution {
    pub fn shortest_path_binary_matrix(grid: Vec<Vec<i32>>) -> i32 {
        if grid[0][0] == 1 {
            -1
        } else {
            let mut q = std::collections::VecDeque::<(i32, i32)>::new();
            q.push_back((0, 0));
            let n = grid.len() as i32;
            let mut size = 1;
            let mut step = 1;
            let mut used = vec![vec![false; n as usize]; n as usize];
            while let Some((x, y)) = q.pop_front() {
                if x == n - 1 && y == n - 1 {
                    return step;
                }
                for dir in dirs2 {
                    let nx = x + dir[0];
                    let ny = y + dir[1];
                    if nx >= 0
                        && nx < n
                        && ny >= 0
                        && ny < n
                        && grid[nx as usize][ny as usize] == 0
                        && !used[nx as usize][ny as usize]
                    {
                        used[nx as usize][ny as usize] = true;
                        q.push_back((nx, ny));
                    }
                }
                size -= 1;
                if size == 0 {
                    size = q.len();
                    step += 1;
                }
            }
            -1
        }
    }
}