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.The number of elements of the given matrix will not exceed 10,000.
2.There are at least one 0 in the given matrix.
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)
533 Lonely Pixel II
547 Friend Circles
Last modified 2yr ago
Copy link
Contents
542. 01 Matrix
1. Question
2. Implementation
3. Time & Space Complexity