1. 题目描述

给定一个由 0 和 1 组成的矩阵，找出每个元素到最近的 0 的距离。
两个相邻元素间的距离为 1 。

2. 题解

广度优先搜索

3. 代码

class Solution {
public:
    vector<vector<int>> updateMatrix(vector<vector<int>>& matrix) {
        int m=matrix.size();
        if (!m) return {};
        int n=matrix[0].size();
        vector<vector<int>> dp(m,vector<int>(n,-1));
        queue<pair<int,int>> que;
        for (int i=0;i<m;i++){
            for (int j=0;j<n;j++){
                if (!matrix[i][j]) {
                    dp[i][j]=0;
                    que.push({i,j});
                }
            }
        }

        int d[4][2]={0,1,1,0,0,-1,-1,0};
        while (!que.empty()){
            int cnt=que.size();
            while (cnt--){
                pair<int,int> tmp=que.front();
                que.pop();
                for (int k=0;k<4;k++){
                    int x=tmp.first;
                    int y=tmp.second;
                    int xx=x+d[k][0];
                    int yy=y+d[k][1];
                    if (xx<0||yy<0||xx>=m||yy>=n||dp[xx][yy]!=-1) continue;
                    dp[xx][yy]=dp[x][y]+1;
                    que.push({xx,yy});
                }
            }
        }
        return dp;
    }
};