题目
https://leetcode.com/problems/01-matrix/
题解
这题很有趣,图解一下思路吧~
可以想象成“感染”的过程。
从 1 开始逐层向外扩散,感染的数字 depth 每轮 +1,直到所有格子全部感染为止。
为了避免重复路径,每次判断即将感染的格子是否大于当前的感染数字 depth。
class Solution {
int M;
int N;
public int[][] updateMatrix(int[][] mat) {
int count = 0;
M = mat.length;
N = mat[0].length;
int[][] dst = new int[M][N]; // distance
for (int i = 0; i < M; i++) {
for (int j = 0; j < N; j++) {
if (mat[i][j] == 0) {
dst[i][j] = 0;
count++;
} else {
dst[i][j] = Integer.MAX_VALUE;
}
}
}
int depth = 0;
while (count != M * N) {
for (int i = 0; i < M; i++) {
for (int j = 0; j < N; j++) {
if (dst[i][j] == depth) {
if (i > 0 && depth + 1 < dst[i - 1][j]) { // left
dst[i - 1][j] = depth + 1;
count++;
}
if (i < M - 1 && depth + 1 < dst[i + 1][j]) { // right
dst[i + 1][j] = depth + 1;
count++;
}
if (j > 0 && depth + 1 < dst[i][j - 1]) { // up
dst[i][j - 1] = depth + 1;
count++;
}
if (j < N - 1 && depth + 1 < dst[i][j + 1]) { // down
dst[i][j + 1] = depth + 1;
count++;
}
}
}
}
depth++;
}
return dst;
}
}