542.01 Matrix
===

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

[542. 01 Matrix](https://leetcode.com/problems/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^4^
* 1 <= `m * n` <= 10^4^
* `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;
}

> 先貼答案，不然我弟寫太好了下午就不敢貼了。
> [name=Marsgoat][time=17 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;
}

> [name=Sheep][time=17 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;
    }
}

> [name=Jim][time=Aug 17, 2023]
### Reference

[回到題目列表](https://marsgoat.github.io/XNnote/coding/leetcodeEveryDay.html)