leetcode542. 01 矩阵
给定一个由 0 和 1 组成的矩阵，找出每个元素到最近的 0 的距离。
两个相邻元素间的距离为 1 。
示例 1:
输入:
0 0 0
0 1 0
0 0 0
输出:
0 0 0
0 1 0
0 0 0
示例 2:
输入:
0 0 0
0 1 0
1 1 1
输出:
0 0 0
0 1 0
1 2 1
bfs先把所有的0都放进队列里面，然后再向周围拓展就行了，和1162题一样。
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
| public int[][] updateMatrix(int[][] matrix) {
int[][] arr = new int[matrix.length][matrix[0].length];
for (int i = 0; i < arr.length; i++) {
Arrays.fill(arr[i], 100001);
}
Queue<int[]> queue = new LinkedList<>();
int[][] direction = {{0,1}, {1,0}, {0,-1}, {-1,0}};
for (int i = 0; i < matrix.length; i++) {
for (int j = 0; j < matrix[i].length; j++) {
if (matrix[i][j] == 0) {
arr[i][j] = 0;
queue.offer(new int[]{i, j});
}
}
}
while (!queue.isEmpty()) {
int[] out = queue.poll();
int x = out[0];
int y = out[1];
int num = arr[x][y];
for (int i = 0; i < 4; i++) {
int nextX = x + direction[i][0];
int nextY = y + direction[i][1];
if (nextX < 0 || nextY < 0 || nextX > matrix.length - 1 || nextY > matrix[0].length - 1)
continue;
if (arr[nextX][nextY] < 100001)
continue;
arr[nextX][nextY] = num + 1;
queue.offer(new int[]{nextX, nextY});
}
}
return arr;
}
|
leetcode 80/100