01 Matrix

class Solution {
public:
    vector<vector<int>> updateMatrix(vector<vector<int>>& mat) {
        int m = mat.size(), n = mat[0].size();
        vector<vector<int>> dist(m, vector<int>(n, INT_MAX));
        queue<pair<int,int>> q;
        for (int r = 0; r < m; ++r)
            for (int c = 0; c < n; ++c)
                if (mat[r][c] == 0) { dist[r][c] = 0; q.push({r, c}); }
        int dr[4] = {1,-1,0,0}, dc[4] = {0,0,1,-1};
        while (!q.empty()) {
            auto [r, c] = q.front(); q.pop();
            for (int k = 0; k < 4; ++k) {
                int nr = r + dr[k], nc = c + dc[k];
                if (nr < 0 || nr >= m || nc < 0 || nc >= n) continue;
                if (dist[nr][nc] > dist[r][c] + 1) {
                    dist[nr][nc] = dist[r][c] + 1;
                    q.push({nr, nc});
                }
            }
        }
        return dist;
    }
};

func updateMatrix(mat [][]int) [][]int {
    m, n := len(mat), len(mat[0])
    dist := make([][]int, m)
    for i := range dist {
        dist[i] = make([]int, n)
        for j := range dist[i] {
            dist[i][j] = math.MaxInt32
        }
    }
    type cell struct{ r, c int }
    q := make([]cell, 0, m*n)
    for r := 0; r < m; r++ {
        for c := 0; c < n; c++ {
            if mat[r][c] == 0 {
                dist[r][c] = 0
                q = append(q, cell{r, c})
            }
        }
    }
    dr := [4]int{1, -1, 0, 0}
    dc := [4]int{0, 0, 1, -1}
    for len(q) > 0 {
        cur := q[0]
        q = q[1:]
        for k := 0; k < 4; k++ {
            nr, nc := cur.r+dr[k], cur.c+dc[k]
            if nr < 0 || nr >= m || nc < 0 || nc >= n {
                continue
            }
            if dist[nr][nc] > dist[cur.r][cur.c]+1 {
                dist[nr][nc] = dist[cur.r][cur.c] + 1
                q = append(q, cell{nr, nc})
            }
        }
    }
    return dist
}

from collections import deque
from typing import List

class Solution:
    def updateMatrix(self, mat: List[List[int]]) -> List[List[int]]:
        m, n = len(mat), len(mat[0])
        dist = [[float('inf')] * n for _ in range(m)]
        q = deque()
        for r in range(m):
            for c in range(n):
                if mat[r][c] == 0:
                    dist[r][c] = 0
                    q.append((r, c))
        dirs = ((1, 0), (-1, 0), (0, 1), (0, -1))
        while q:
            r, c = q.popleft()
            for dr, dc in dirs:
                nr, nc = r + dr, c + dc
                if 0 <= nr < m and 0 <= nc < n and dist[nr][nc] > dist[r][c] + 1:
                    dist[nr][nc] = dist[r][c] + 1
                    q.append((nr, nc))
        return dist

var updateMatrix = function(mat) {
    const m = mat.length, n = mat[0].length;
    const dist = Array.from({ length: m }, () => Array(n).fill(Infinity));
    const q = [];
    for (let r = 0; r < m; r++) {
        for (let c = 0; c < n; c++) {
            if (mat[r][c] === 0) {
                dist[r][c] = 0;
                q.push([r, c]);
            }
        }
    }
    const dr = [1, -1, 0, 0], dc = [0, 0, 1, -1];
    let head = 0;
    while (head < q.length) {
        const [r, c] = q[head++];
        for (let k = 0; k < 4; k++) {
            const nr = r + dr[k], nc = c + dc[k];
            if (nr < 0 || nr >= m || nc < 0 || nc >= n) continue;
            if (dist[nr][nc] > dist[r][c] + 1) {
                dist[nr][nc] = dist[r][c] + 1;
                q.push([nr, nc]);
            }
        }
    }
    return dist;
};

class Solution {
    public int[][] updateMatrix(int[][] mat) {
        int m = mat.length, n = mat[0].length;
        int[][] dist = new int[m][n];
        for (int[] row : dist) Arrays.fill(row, Integer.MAX_VALUE);
        Deque<int[]> q = new ArrayDeque<>();
        for (int r = 0; r < m; r++) {
            for (int c = 0; c < n; c++) {
                if (mat[r][c] == 0) {
                    dist[r][c] = 0;
                    q.offer(new int[]{r, c});
                }
            }
        }
        int[] dr = {1, -1, 0, 0};
        int[] dc = {0, 0, 1, -1};
        while (!q.isEmpty()) {
            int[] cur = q.poll();
            int r = cur[0], c = cur[1];
            for (int k = 0; k < 4; k++) {
                int nr = r + dr[k], nc = c + dc[k];
                if (nr < 0 || nr >= m || nc < 0 || nc >= n) continue;
                if (dist[nr][nc] > dist[r][c] + 1) {
                    dist[nr][nc] = dist[r][c] + 1;
                    q.offer(new int[]{nr, nc});
                }
            }
        }
        return dist;
    }
}

function updateMatrix(mat: number[][]): number[][] {
    const m = mat.length, n = mat[0].length;
    const dist: number[][] = Array.from({ length: m }, () => Array(n).fill(Infinity));
    const q: [number, number][] = [];
    for (let r = 0; r < m; r++) {
        for (let c = 0; c < n; c++) {
            if (mat[r][c] === 0) {
                dist[r][c] = 0;
                q.push([r, c]);
            }
        }
    }
    const dr = [1, -1, 0, 0], dc = [0, 0, 1, -1];
    let head = 0;
    while (head < q.length) {
        const [r, c] = q[head++];
        for (let k = 0; k < 4; k++) {
            const nr = r + dr[k], nc = c + dc[k];
            if (nr < 0 || nr >= m || nc < 0 || nc >= n) continue;
            if (dist[nr][nc] > dist[r][c] + 1) {
                dist[nr][nc] = dist[r][c] + 1;
                q.push([nr, nc]);
            }
        }
    }
    return dist;
}