LeetCode.542.01 Matrix 01矩阵

题目描述

542 01 Matrix
https://leetcode-cn.com/problems/01-matrix/

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:
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.

---

解题过程

相似题目
LeetCode.994.Rotting Oranges 腐烂的橘子
LeetCode.1162.As Far from Land as Possible 离所有陆地最远的海洋/地图分析
LeetCode.542.01 Matrix 01矩阵

两个 bfs 解法：
1、广度优先搜索： 从每个 1 开始一次广度优先搜索，找到离这个 1 最近的 0。时间复杂度 O(m^2n^2)
2、多源广度优先搜索：把所有 0 加入队列开始广度优先搜索，在搜索过程中第 n 层到达的 1 的最近距离就是 n。时间复杂度 O(mn)

推荐使用多源广度优先搜索，因为多源广度优先搜索比进行 mn 次广度优先搜索的时间复杂度低两个数量级，某些题虽然两者都能做，但不使用多源广度优先搜索就会超时。

广度优先搜索

时间复杂度 O(m^2n^2)，空间复杂度O(mn)

private static class SolutionV2020 {
    int[] dx = {-1, 0, 1,  0};
    int[] dy = { 0, 1, 0, -1};
    int nrows, ncolumns;
    public int[][] updateMatrix(int[][] matrix) {
        if (null == matrix) {
            return null;
        }
        this.nrows = matrix.length;
        this.ncolumns = matrix[0].length;
        int[][] res = new int[nrows][ncolumns];

        for (int i = 0; i < nrows; i++) {
            for (int j = 0; j < ncolumns; j++) {
                if (matrix[i][j] == 1) {
                    res[i][j] = bfs(matrix, i, j);
                }
            }
        }
        return res;
    }

    // 从 i,j 开始一次bfs，返回首次遇到0时的层数
    private int bfs(int[][] matrix, int i, int j) {
        // 已访问结点集合
        Set<Pair<Integer, Integer>> visited = new HashSet<>();
        Queue<Pair<Integer, Integer>> queue = new LinkedList<>();
        queue.offer(new Pair<>(i, j));
        int level = 0;
        while (!queue.isEmpty()) {
            int size = queue.size();
            // 遍历当前层的所有结点
            for (int l = 0; l < size; l++) {
                Pair<Integer, Integer> pair = queue.poll();
                visited.add(pair);
                // 遇到0直接结束
                if (matrix[pair.getKey()][pair.getValue()] == 0) {
                    return level;
                }
                // 上下左右的结点
                for (int k = 0; k < 4; k++) {
                    int ii = pair.getKey() + dx[k];
                    int jj = pair.getValue() + dy[k];
                    if (ii >= 0 && ii < nrows && jj >= 0 && jj < ncolumns && !visited.contains(new Pair<>(ii, jj))) {
                        queue.offer(new Pair<>(ii, jj));
                    }
                }
            }
            level++;
        }
        return level;
    }
}

多源广度优先搜索

---

GitHub代码

algorithms/leetcode/leetcode/_542_01Matrix.java
https://github.com/masikkk/algorithms/blob/master/leetcode/leetcode/_542_01Matrix.java

---