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) {
            return matrix;
        }

        int m = matrix.length, n = matrix[0].length;
        int[][] res = new int[m][n];

        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) {
                    search(i, j, matrix, res, directions);
                }
            }
        }
        return res;
    }

    public void search(int row, int col, int[][] matrix, int[][] res, int[][] directions) {
        Queue<int[]> queue = new LinkedList();
        queue.add(new int[] {row, col});
        int dist = 0;

        while (!queue.isEmpty()) {
            int size = queue.size();
            while (size-- > 0) {
                int[] curCell = queue.remove();
                int curRow = curCell[0];
                int curCol = curCell[1];

                if (matrix[curRow][curCol] == 0) {
                    res[row][col] = dist;
                    return;
                }

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

                    if (nextRow < 0 || nextRow >= matrix.length || nextCol < 0 || nextCol >= matrix[0].length) continue;

                    queue.add(new int[] {nextRow, nextCol});
                }
            }
            ++dist;
        }
    }
}

(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)