542 01 Matrix 01 矩阵

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

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.

题目描述:
给定一个由 0 和 1 组成的矩阵，找出每个元素到最近的 0 的距离。

两个相邻元素间的距离为 1 。

示例 :

示例 1：

输入：
[[0,0,0],
[0,1,0],
[0,0,0]]

输出：
[[0,0,0],
[0,1,0],
[0,0,0]]

示例 2：

输入：
[[0,0,0],
[0,1,0],
[1,1,1]]

输出：
[[0,0,0],
[0,1,0],
[1,2,1]]

提示:

给定矩阵的元素个数不超过 10000。
给定矩阵中至少有一个元素是 0。
矩阵中的元素只在四个方向上相邻: 上、下、左、右。

思路:

BFS
可以先只查找左上的部分, 再查找右下的部分, 取两部分到 0 的距离的最小值
时间复杂度 O(mn), 空间复杂度 O(1)

代码:
C++:

class Solution 
{
public:
    vector<vector<int>> updateMatrix(vector<vector<int>>& matrix) 
    {
        int m = matrix.size(), n = matrix[0].size();
        vector<vector<int>> result(m, vector<int>(n, 0x3f3f3f3f));
        for (int i = 0; i < m; i++) for (int j = 0; j < n; j++) if (matrix[i][j] == 0)  result[i][j] = 0;
        for (int i = 0; i < m; ++i) 
        {
            for (int j = 0; j < n; ++j) 
            {
                if (i - 1 >= 0) result[i][j] = min(result[i][j], result[i - 1][j] + 1);
                if (j - 1 >= 0) result[i][j] = min(result[i][j], result[i][j - 1] + 1);
            }
        }
        for (int i = m - 1; i >= 0; i--) 
        {
            for (int j = n - 1; j >= 0; j--) 
            {
                if (i + 1 < m) result[i][j] = min(result[i][j], result[i + 1][j] + 1);
                if (j + 1 < n) result[i][j] = min(result[i][j], result[i][j + 1] + 1);
            }
        }
        return result;
    }
};

Java:

class Solution {
    public int[][] updateMatrix(int[][] matrix) {
        int m = matrix.length, n = matrix[0].length;
        int[][] result = new int[m][n];
        for (int i = 0; i < m; i++) Arrays.fill(result[i], 0x3f3f3f3f);
        for (int i = 0; i < m; i++) for (int j = 0; j < n; j++) if (matrix[i][j] == 0)  result[i][j] = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (i - 1 >= 0) result[i][j] = Math.min(result[i][j], result[i - 1][j] + 1);
                if (j - 1 >= 0) result[i][j] = Math.min(result[i][j], result[i][j - 1] + 1);
            }
        }
        for (int i = m - 1; i >= 0; --i) {
            for (int j = n - 1; j >= 0; --j) {
                if (i + 1 < m) result[i][j] = Math.min(result[i][j], result[i + 1][j] + 1);
                if (j + 1 < n) result[i][j] = Math.min(result[i][j], result[i][j + 1] + 1);
            }
        }
        return result;
    }
}

Python:

class Solution:
    def updateMatrix(self, matrix: List[List[int]]) -> List[List[int]]:
        m, n, d = len(matrix), len(matrix[0]), [(0, 1), (1, 0), (0, -1), (-1, 0)]
        queue = [(i, j) for i in range(m) for j in range(n) if not matrix[i][j]]
        visited = set(queue)
        while queue:
            x, y = queue.pop(0)
            for dx, dy in d:
                i, j = x + dx, y + dy
                if -1 < i < m and -1 < j < n and (i, j) not in visited:
                    matrix[i][j] = matrix[x][y] + 1
                    visited.add((i, j))
                    queue.append((i, j))
        return matrix