Given a matrix consists of 0 and 1, find the distance of the nearest 0 for each cell.
The distance between two adjacent cells is 1.
Example
No.1
Input:
1
2
3
|
[[0,0,0],
[0,1,0],
[0,0,0]]
|
Output:
1
2
3
|
[[0,0,0],
[0,1,0],
[0,0,0]]
|
No.2
Input:
1
2
3
|
[[0,0,0],
[0,1,0],
[1,1,1]]
|
Output:
1
2
3
|
[[0,0,0],
[0,1,0],
[1,2,1]]
|
Note
- The number of elements of the given matrix will not exceed 10,000.
- There are at least one 0 in the given matrix.
- The cells are adjacent in only four directions: up, down, left and right.
BFS
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
|
public int[][] updateMatrix(int[][] matrix) {
int m = matrix.length;
int n = matrix[0].length;
int[][] directions = new int[][] {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
Queue<int[]> queue = new LinkedList<>();
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (matrix[i][j] == 0)
queue.offer(new int[] {i, j});
else
matrix[i][j] = Integer.MAX_VALUE;
}
}
while (!queue.isEmpty()) {
int size = queue.size();
for (int i = 0; i < size; i++) {
int[] pos = queue.poll();
for (int[] direction : directions) {
int x = pos[0] + direction[0];
int y = pos[1] + direction[1];
if (x < 0 || y < 0 || x >= m || y >= n || matrix[x][y] <= matrix[pos[0]][pos[1]] + 1)
continue;
matrix[x][y] = matrix[pos[0]][pos[1]] + 1;
queue.offer(new int[] {x, y});
}
}
}
return matrix;
}
|
Other
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 m = matrix.length;
int n = matrix[0].length;
int[][] result = new int[m][n];
for (int i = 0; i < m; i++) {
Arrays.fill(result[i], 10000);
for (int j = 0; j < n; j++) {
if (matrix[i][j] == 0)
result[i][j] = 0;
else {
if (i > 0)
result[i][j] = Math.min(result[i][j], result[i - 1][j] + 1);
if (j > 0)
result[i][j] = Math.min(result[i][j], result[i][j - 1] + 1);
}
}
}
for (int i = m - 1; i >= 0; i--) {
for (int j = n - 1; j >= 0; j--) {
if (result[i][j] > 1) {
if (i + 1 < m)
result[i][j] = Math.min(result[i][j], result[i + 1][j] + 1);
if (j + 1 < n)
result[i][j] = Math.min(result[i][j], result[i][j + 1] + 1);
}
}
}
return result;
}
|
近期评论