[数据结构与算法]01矩阵(c++ bfs解法)

01 矩阵
给定一个由 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]]

提示：

m == mat.length
n == mat[i].length
1 <= m, n <= 104
1 <= m * n <= 104
mat[i][j] is either 0 or 1.
mat 中至少有一个 0
相关标签
广度优先搜索
数组
动态规划
矩阵

我自己的思路：对矩阵中每一个1去寻找与之最近的0，这样如果只有一个0，而且在最后的话，会超出时间限制。

正确解答：对矩阵中每一个0去更新距离它最近的1的距离，同时将更新后的1也作为一个站点去更新另外的1。代码如下：

class Solution {
    int dirs[4][2] = {{-1,0},{1,0},{0,-1},{0,1}};//四个方向
public:
    vector<vector<int>> updateMatrix(vector<vector<int>>& mat) {
        int m=mat.size(),n=mat[0].size();
        vector<vector<int>> dist(m,vector<int>(n));//保存距离
        vector<vector<int>> seen(m,vector<int>(n));//保存已经访问过的点
        queue<pair<int,int>> q;//保存0的点
        for(int i=0;i<m;i++)
        {
            for(int j=0;j<n;j++)
            {
                if(mat[i][j]==0)
                {
                    dist[i][j]=0;
                    q.push(make_pair(i,j));
                    seen[i][j]=1;
                }
            }
        }
        while(!q.empty())
        {
            auto [i,j] = q.front();
            q.pop();
            for(int d=0;d<4;d++)
            {
                int ni=i+dirs[d][0];
                int nj=j+dirs[d][1];
                if(ni>=0&&ni<m&&nj>=0&&nj<n&&!seen[ni][nj])
                {
                    dist[ni][nj]=dist[i][j]+1;
                    seen[ni][nj]=1;
                    q.push(make_pair(ni,nj));
                }
            }
        }
        return dist;
    }
};