542. 01 Matrix
https://leetcode.com/problems/01-matrix/
BFS问题，第一感觉是使用队列来做。先对原数组进行处理，将 0 的下标入队列，非零下标记为最大Integer值。之后由每个0的四周逐渐散开，覆盖掉其四周的 Integer.MAX_VALUE。这样对于处理过的坐标，后续其他 0 散开达到时，其距离一定比当前值大，也就不用处理了。
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
| public int[][] updateMatrix(int[][] matrix) {
if (matrix == null || matrix.length == 0) {
return null;
}
int row = matrix.length;
int col = matrix[0].length;
Queue<int[]> queue = new LinkedList<>();
for (int i = 0; i < row; i++) {
for (int j = 0; j < col; j++) {
if (matrix[i][j] == 0) {
queue.offer(new int[]{i, j});
} else {
matrix[i][j] = Integer.MAX_VALUE;
}
}
}
int[][] neigh = new int[][]{{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
while (!queue.isEmpty()) {
int[] idx = queue.poll();
for (int[] nei : neigh) {
int i = idx[0] + nei[0];
int j = idx[1] + nei[1];
if (i >= 0 && i < row && j >= 0 && j < col
&& matrix[i][j] > matrix[idx[0]][idx[1]] + 1) {
matrix[i][j] = matrix[idx[0]][idx[1]] + 1;
queue.offer(new int[]{i, j});
}
}
}
return matrix;
}
|
