day25-0 1矩阵

目录

题目描述：

示例 1：

示例 2：

解决方案：

函数代码：

题目描述：

给定一个由 0 和 1 组成的矩阵 mat ，请输出一个大小相同的矩阵，其中每一个格子是 mat 中对应位置元素到最近的 0 的距离，两个相邻元素间的距离为 1 。

示例 1：

输入：
mat = [ [0,0,0],
        [0,1,0],
        [0,0,0]]
输出： 
[[0,0,0],
 [0,1,0],
 [0,0,0]]

示例 2：

输入：
mat = [ [0,0,0],
        [0,1,0],
        [1,1,1]]
输出：
[[0,0,0],
 [0,1,0],
 [1,2,1]]

解决方案：

​1、分析结果：每个位置上的值，取决于上下左右的值的变化，0->+1  。
​2、上下左右依次遍历筛选即可。
​3、题目要求最小距离：建立等大容器，先放入无穷大的值，min（）取值。
​4、优化：从左上到右下遍历，再反向查重遍历即右下到左上，不断用min（）更新取值。

函数代码：

class Solution {
public:
    vector<vector<int>> updateMatrix(vector<vector<int>>& mat) {
        if(mat.empty()) return {};
        int row=mat.size();
        int col=mat[0].size();
        vector<vector<int>>dp(row,vector<int>(col,9999));
        for(int i=0;i<row;i++){
            for(int j=0;j<col;j++){
                if(mat[i][j]==0)    dp[i][j]=0;
                if(i>0)             dp[i][j]=min(dp[i][j],dp[i-1][j]+1);
                if(j>0)             dp[i][j]=min(dp[i][j],dp[i][j-1]+1);
            }
        }
        //第二次查重遍历--------------------------
        for(int i=row-1;i>=0;i--){
            for(int j=col-1;j>=0;j--){
                if(mat[i][j]!=0){
                    if(i<row-1)  dp[i][j]=min(dp[i][j],dp[i+1][j]+1);
                    if(j<col-1)  dp[i][j]=min(dp[i][j],dp[i][j+1]+1);
                }
            }
        }

        return dp;
    }
};