542.01 Matrix

tags: Medium Array DP BFS Matrix

542. 01 Matrix

題目描述

Given an m x n binary matrix mat, return the distance of the nearest 0 for each cell.

The distance between two adjacent cells is 1.

範例

Example 1:

Input: mat = [[0,0,0],[0,1,0],[0,0,0]]
Output: [[0,0,0],[0,1,0],[0,0,0]]

Example 2:

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

Constraints:

• m == mat.length
• n == mat[i].length
• 1 <= m, n <= 10⁴
• 1 <= m * n <= 10⁴
• mat[i][j] is either 0 or 1.
• There is at least one 0 in mat.

解答

Javascript

function updateMatrix(mat) {
  const n = mat.length;
  const m = mat[0].length;
  const isInBounds = (i, j) => i >= 0 && i < n && j >= 0 && j < m;

  const queue = [];

  for (let i = 0; i < n; i++) {
    for (let j = 0; j < m; j++) {
      // 將0放進queue中
      if (mat[i][j] === 0) {
        queue.push([i, j, 0]);
      } else {
        mat[i][j] = Infinity; // 先將1設為無限大
      }
    }
  }

  const visited = new Array(n).fill(0).map(() => new Array(m).fill(false));

  while (queue.length) {
    const [x, y, step] = queue.shift();
    const neighbors = [
      [x - 1, y],
      [x + 1, y],
      [x, y - 1],
      [x, y + 1],
    ];

    for (const neighbor of neighbors) {
      const [i, j] = neighbor;
      if (isInBounds(i, j) && !visited[i][j]) {
        mat[i][j] = Math.min(mat[i][j], step + 1); // 更新最短距離
        queue.push([i, j, step + 1]);
        visited[i][j] = true;
      }
    }
  }

  return mat;
}

先貼答案，不然我弟寫太好了下午就不敢貼了。
Marsgoat17 Aug 2023

TypeScript

function updateMatrix(mat: number[][]): number[][] {
  const m = mat.length;
  const n = mat[0].length;
  const MAX_DISTANCE = m + n;
  const directions = [
    [1, 0], // 下
    [-1, 0], // 上
    [0, 1], // 右
    [0, -1], // 左
  ];
  const queue: [number, number][] = [];
  const visited = new Array(m).fill(0).map(() => new Array(n).fill(false));

  // 初始化
  for (let i = 0; i < m; i++) {
    for (let j = 0; j < n; j++) {
      if (mat[i][j] === 0) {
        queue.push([i, j]);
        visited[i][j] = true;
      } else {
        mat[i][j] = MAX_DISTANCE;
      }
    }
  }

  // BFS
  while (queue.length > 0) {
    const [i, j] = queue.shift()!;
    for (const [di, dj] of directions) {
      const ni = i + di;
      const nj = j + dj;
      if (ni >= 0 && ni < m && nj >= 0 && nj < n && !visited[ni][nj]) {
        visited[ni][nj] = true;
        mat[ni][nj] = mat[i][j] + 1;
        queue.push([ni, nj]);
      }
    }
  }

  return mat;
}

Sheep17 Aug 2023

C#

public class Solution {
    public int[][] UpdateMatrix(int[][] mat) {
        int m = mat.Length, n = mat[0].Length;
        bool IsValidIndex(int x, int y) => 0 <= x && x < m && 0 <= y && y < n;
        
        List<(int x, int y)> directions = new() {
            (1,0), (0, 1), (-1,0), (0,-1)
        };

        Queue<(int x, int y)> queue = new();

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (mat[i][j] == 0) {
                    queue.Enqueue((i, j));
                } else {
                    mat[i][j] = int.MaxValue;
                }
            }
        }

        while (queue.Any()) {
            (int x, int y) = queue.Dequeue();
            
            foreach ((int dx, int dy) in directions) {
                (int px, int py) = (x + dx, y + dy);                
                if (IsValidIndex(px, py) && mat[px][py] == int.MaxValue) {
                    mat[px][py] = mat[x][y] + 1;
                    queue.Enqueue((px, py));
                }
            }
        }

        return mat;
    }
}

JimAug 17, 2023

Reference

回到題目列表