代码是比较好写出来，但是这个DP的思路还是有点不清楚

class Solution {
public:
    vector<vector<int>> updateMatrix(vector<vector<int>>& mat) {
        int m = mat.size(), n = mat[0].size();
        vector<vector<int>> dp(m, vector<int>(n, INT_MAX - 1));
        for (int i = 0; i < m; i ++) {
            for (int j = 0; j < n; j ++) {
                if (mat[i][j] == 0) {
                    dp[i][j] = 0;
                } else {
                    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 = m - 1; i >= 0; i --) {
            for (int j = n - 1; j >= 0; j --) {
                if (mat[i][j] != 0) {
                    if (i < m - 1) {
                        dp[i][j] = min(dp[i][j], dp[i + 1][j] + 1);
                    }
                    if (j < n - 1) {
                        dp[i][j] = min(dp[i][j], dp[i][j + 1] + 1);
                    }
                }
            }
        }
        return dp;
    }
};

BFS

从 所有的 0 开始遍历

https://www.acwing.com/solution/content/425/

class Solution {
public:
    vector<vector<int>> updateMatrix(vector<vector<int>>& mat) {
        int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
        queue<pair<int, int>> q;
        int n = mat.size(), m = mat[0].size();
        vector<vector<int>> dis(n, vector<int>(m, -1));
	
				// 初始化 queue 和 dis 数组
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (mat[i][j] == 0) {
                    dis[i][j] = 0;
                    q.push({i, j});
                }
            }
        }

        while (!q.empty()) {
            auto p = q.front(); q.pop();
            for (int k = 0; k < 4; k++) {
                int x = p.first + dx[k];
                int y = p.second + dy[k];
                if (x >= 0 && x < mat.size() && y >= 0 && y < mat[0].size() && dis[x][y] == -1) {
                    dis[x][y] = dis[p.first][p.second] + 1;
                    q.push({x, y});
                }
            }
        }
        return dis;
    }
};

从 1 开始 BFS 超时了

class Solution {
public:
    vector<vector<int>> updateMatrix(vector<vector<int>>& mat) {
        int n = mat.size(), m = mat[0].size();
        vector<vector<int>> res(n, vector<int>(m, 0));
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (mat[i][j] == 0) continue;
                else {
                    res[i][j] = bfs(mat, i, j);
                }
            }
        }
        return res;
    }

    int bfs(const vector<vector<int>>& mat, int i, int j) {
        int n = mat.size(), m = mat[0].size();
        vector<vector<bool>> visited(n, vector<bool>(m, 0));
        queue<pair<int, int>> q;
        q.push({i, j});
        int distance = 0;
        int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
        while (!q.empty()) {
            distance++;
            int size = q.size();
            for (int i = 0; i < size; i++) {
                auto p = q.front(); q.pop();
                for (int k = 0; k < 4; k++) {
                    int x = p.first + dx[k];
                    int y = p.second + dy[k];
                    if (x >= 0 && x < mat.size() && y >= 0 && y < mat[0].size() && !visited[x][y]) {
                        if (mat[x][y] == 0) {
                            return distance;
                        } else {
                            q.push({x, y});
                            visited[x][y] = 1;
                        }
                    }
                }
            }
        }
        return distance;
    }
};