友情支持
如果您觉得这个笔记对您有所帮助，看在D瓜哥码这么多字的辛苦上，请友情支持一下，D瓜哥感激不尽，😜
|
|
有些打赏的朋友希望可以加个好友，欢迎关注D 瓜哥的微信公众号，这样就可以通过公众号的回复直接给我发信息。
公众号的微信号是: jikerizhi。因为众所周知的原因，有时图片加载不出来。 如果图片加载不出来可以直接通过搜索微信号来查找我的公众号。 |
542. 01 矩阵
给定一个由 0 和 1 组成的矩阵 mat ，请输出一个大小相同的矩阵，其中每一个格子是 mat 中对应位置元素到最近的 0 的距离。
两个相邻元素间的距离为 1 。
示例 1：
输入：mat = [[0,0,0],[0,1,0],[0,0,0]] 输出：[[0,0,0],[0,1,0],[0,0,0]]
示例 2：
输入：mat = [[0,0,0],[0,1,0],[1,1,1]] 输出：[[0,0,0],[0,1,0],[1,2,1]]
提示：
-
m == mat.length -
n == mat[i].length -
1 <= m, n <= 104 -
1 <= m * n <= 104 -
mat[i][j] is either 0 or 1. -
mat中至少有一个0
思路分析
多源广度优先。以 0 为起点，向 1 广播，遇到 1 就停止，否则就继续向外广播。
-
一刷
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
/**
* @author D瓜哥 · https://www.diguage.com
* @since 2026-03-07 22:47:35
*/
public int[][] updateMatrix(int[][] mat) {
Queue<int[]> queue = new ArrayDeque<>();
int row = mat.length;
int column = mat[0].length;
for (int r = 0; r < row; r++) {
for (int c = 0; c < column; c++) {
if (mat[r][c] == 0) {
queue.offer(new int[]{r, c});
} else {
mat[r][c] = -1;
}
}
}
int[] dx = new int[]{0, 0, -1, 1};
int[] dy = new int[]{-1, 1, 0, 0};
while (!queue.isEmpty()) {
int[] point = queue.poll();
int r = point[0];
int c = point[1];
for (int i = 0; i < 4; i++) {
int nr = r + dx[i];
int nc = c + dy[i];
if (0 <= nr && nr < row
&& 0 <= nc && nc < column
&& mat[nr][nc] == -1) {
mat[nr][nc] = mat[r][c] + 1;
queue.offer(new int[]{nr, nc});
}
}
}
return mat;
}