01 Matrix
Calculate distance to nearest 0 for each cell using multi-source BFS
Calculate the shortest distance from each cell to the nearest 0
問題描述
給定一個由 0 和 1 組成的矩陣 mat，請輸出一個大小相同的矩陣，其中每一個格子是 mat 中對應位置元素到最近的 0 的距離。
兩個相鄰元素間的距離為 1。
範例
輸入：mat = [[0,0,0],[0,1,0],[0,0,0]]
輸出：[[0,0,0],[0,1,0],[0,0,0]]
輸入：mat = [[0,0,0],[0,1,0],[1,1,1]]
輸出：[[0,0,0],[0,1,0],[1,2,1]]
限制條件
m == mat.lengthn == mat[i].length1 <= m, n <= 10⁴1 <= m * n <= 10⁴mat[i][j]是0或1mat中至少有一個0
解題思路
### 多源 BFS 起點 將所有值為 0 的位置作為 BFS 的起始點
### 同時擴散 從所有 0 位置同時開始 BFS 擴散，計算距離
### 四個方向遍歷 對每個位置檢查上下左右四個方向的相鄰位置
解決方案
interface Cell {
x: number;
y: number;
distance: number;
}
type Matrix = number[][];
export function updateMatrix(mat: Matrix): Matrix {
const HEIGHT = mat.length;
const WIDTH = mat[0].length;
if (HEIGHT === 1 && WIDTH === 1) {
return [[mat[0][0]]];
}
const distances = Array.from({ length: HEIGHT }, () =>
Array.from({ length: WIDTH }).fill(Infinity),
) as Matrix;
const bfsQueue: Cell[] = [];
mat.forEach((row, x) => {
row.forEach((cell, y) => {
if (cell === 0) {
distances[x][y] = 0;
bfsQueue.push({ x, y, distance: 0 });
}
});
});
if (bfsQueue.length === 0) {
return mat;
}
const DIRECTIONS = [
[-1, 0], // up
[0, 1], // right
[1, 0], // down
[0, -1], // left
] as const;
while (bfsQueue.length > 0) {
const currentCell = bfsQueue.shift()!;
DIRECTIONS.forEach(([dx, dy]) => {
const nextX = currentCell.x + dx;
const nextY = currentCell.y + dy;
const isInBounds = nextX >= 0 && nextX < HEIGHT && nextY >= 0 && nextY < WIDTH;
if (isInBounds) {
const newDistance = currentCell.distance + 1;
const canUpdate = distances[nextX][nextY] > newDistance;
if (canUpdate) {
distances[nextX][nextY] = newDistance;
bfsQueue.push({
x: nextX,
y: nextY,
distance: newDistance,
});
}
}
});
}
return distances;
}