542 01 Matrix

542. 01 Matrix

1. Question

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 1: Input:
1
0 0 0
2
0 1 0
3
0 0 0
Copied!
Output:
1
0 0 0
2
0 1 0
3
0 0 0
Copied!
Example 2: Input:
1
0 0 0
2
0 1 0
3
1 1 1
Copied!
Output:
1
0 0 0
2
0 1 0
3
1 2 1
Copied!
Note:
  1. 1.
    The number of elements of the given matrix will not exceed 10,000.
  2. 2.
    There are at least one 0 in the given matrix.
  3. 3.
    The cells are adjacent in only four directions: up, down, left and right.

2. Implementation

(1) BFS
1
class Solution {
2
public int[][] updateMatrix(int[][] matrix) {
3
if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
4
return matrix;
5
}
6
7
Queue<int[]> queue = new LinkedList<>();
8
int m = matrix.length, n = matrix[0].length;
9
int[][] directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
10
11
for (int i = 0; i < m; i++) {
12
for (int j = 0; j < n; j++) {
13
if (matrix[i][j] == 0) {
14
queue.add(new int[] {i, j});
15
}
16
else {
17
matrix[i][j] = Integer.MAX_VALUE;
18
}
19
}
20
}
21
22
while (!queue.isEmpty()) {
23
int[] cell = queue.remove();
24
int curRow = cell[0], curCol = cell[1];
25
26
for (int[] direction : directions) {
27
int nextRow = curRow + direction[0];
28
int nextCol = curCol + direction[1];
29
30
if (isValid(matrix, curRow, curCol, nextRow, nextCol)) {
31
matrix[nextRow][nextCol] = matrix[curRow][curCol] + 1;
32
queue.add(new int[] {nextRow, nextCol});
33
}
34
}
35
}
36
return matrix;
37
}
38
39
public boolean isValid(int[][] matrix, int curRow, int curCol, int nextRow, int nextCol) {
40
return nextRow >= 0 && nextRow < matrix.length && nextCol >= 0 && nextCol < matrix[0].length && matrix[nextRow][nextCol] > matrix[curRow][curCol] + 1;
41
}
42
}
Copied!
(2) DFS
1
class Solution {
2
public int[][] updateMatrix(int[][] matrix) {
3
if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
4
return matrix;
5
}
6
7
int m = matrix.length, n = matrix[0].length;
8
int[][] directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
9
10
for (int i = 0; i < m; i++) {
11
for (int j = 0; j < n; j++) {
12
if (matrix[i][j] != 0) {
13
dfs(i, j, matrix, directions);
14
}
15
}
16
}
17
return matrix;
18
}
19
20
public void dfs(int row, int col, int[][] matrix, int[][] directions) {
21
int dist = Integer.MAX_VALUE;
22
23
for (int[] direction : directions) {
24
int nextRow = row + direction[0];
25
int nextCol = col + direction[1];
26
27
if (isValid(nextRow, nextCol, matrix)) {
28
dist = Math.min(dist, matrix[nextRow][nextCol] + 1);
29
}
30
}
31
32
if (dist != matrix[row][col]) {
33
matrix[row][col] = dist;
34
35
for (int[] direction : directions) {
36
int nextRow = row + direction[0];
37
int nextCol = col + direction[1];
38
39
if (isValid(nextRow, nextCol, matrix)) {
40
dfs(nextRow, nextCol, matrix, directions);
41
}
42
}
43
}
44
}
45
46
public boolean isValid(int nextRow, int nextCol, int[][] matrix) {
47
return nextRow >= 0 && nextRow < matrix.length && nextCol >= 0 && nextCol < matrix[0].length;
48
}
49
}
Copied!

3. Time & Space Complexity

BFS: 时间复杂度O(mn), 空间复杂度O(mn)
DFS: 时间复杂度O(mn), 空间复杂度O(mn)