Steward

分享是一種喜悅、更是一種幸福

程式語言 - LeetCode - C++ - 542. 01 Matrix

---

題目：


解答：

class Solution {
public:
    vector<vector<int>> updateMatrix(vector<vector<int>>& mat) {
        int m = mat.size();
        int n = mat[0].size();
        queue<pair<int, int>> q;

        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (mat[i][j] == 0) {
                    q.push({ i, j });
                }
                else {
                    mat[i][j] = INT_MAX;
                }
            }
        }

        vector<pair<int, int>> dir = {
            { -1, 0 }, { 0, -1 }, { 1, 0 }, { 0, 1 }
        };

        while (!q.empty()) {
            auto [x, y] = q.front();

            q.pop();
            for (auto& [dx, dy] : dir) {
                int yy = y + dy;
                int xx = x + dx;

                if (xx < 0 || xx >= m || yy < 0 || yy >= n) {
                    continue;
                }

                if (mat[xx][yy] > mat[x][y] + 1) {
                    mat[xx][yy] = mat[x][y] + 1;
                    q.push({ xx, yy });
                }
            }
        }

        return mat;
    }
};