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:

0 0 0
0 1 0
0 0 0

Output:

0 0 0
0 1 0
0 0 0

Example 2: Input:

0 0 0
0 1 0
1 1 1

Output:

0 0 0
0 1 0
1 2 1

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

class Solution {
    public int[][] updateMatrix(int[][] matrix) {
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
            return matrix;
        }

        Queue<int[]> queue = new LinkedList<>();
        int m = matrix.length, n = matrix[0].length;
        int[][] directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (matrix[i][j] == 0) {
                    queue.add(new int[] {i, j});
                }
                else {
                    matrix[i][j] = Integer.MAX_VALUE;
                }
            }
        }

        while (!queue.isEmpty()) {
            int[] cell = queue.remove();
            int curRow = cell[0], curCol = cell[1];

            for (int[] direction : directions) {
                int nextRow = curRow + direction[0];
                int nextCol = curCol + direction[1];

                if (isValid(matrix, curRow, curCol, nextRow, nextCol)) {
                    matrix[nextRow][nextCol] = matrix[curRow][curCol] + 1;
                    queue.add(new int[] {nextRow, nextCol});
                }
            }
        }
        return matrix;
    }

    public boolean isValid(int[][] matrix, int curRow, int curCol, int nextRow, int nextCol) {
        return nextRow >= 0 && nextRow < matrix.length && nextCol >= 0 && nextCol < matrix[0].length && matrix[nextRow][nextCol] > matrix[curRow][curCol] + 1;
    }
}

(2) DFS

class Solution {
    public int[][] updateMatrix(int[][] matrix) {
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
            return matrix;
        }

        int m = matrix.length, n = matrix[0].length;
        int[][] directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (matrix[i][j] != 0) {
                    dfs(i, j, matrix, directions);
                }
            }
        }
        return matrix;
    }

    public void dfs(int row, int col, int[][] matrix, int[][] directions) {
        int dist = Integer.MAX_VALUE;

        for (int[] direction : directions) {
            int nextRow = row + direction[0];
            int nextCol = col + direction[1];

            if (isValid(nextRow, nextCol, matrix)) {
                dist = Math.min(dist, matrix[nextRow][nextCol] + 1);
            }
        }

        if (dist != matrix[row][col]) {
            matrix[row][col] = dist;

            for (int[] direction : directions) {
                int nextRow = row + direction[0];
                int nextCol = col + direction[1];

                if (isValid(nextRow, nextCol, matrix)) {
                    dfs(nextRow, nextCol, matrix, directions);
                }
            }
        }
    }

    public boolean isValid(int nextRow, int nextCol, int[][] matrix) {
        return nextRow >= 0 && nextRow < matrix.length && nextCol >= 0 && nextCol < matrix[0].length;
    }
}

3. Time & Space Complexity

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

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