題目網址：https://leetcode.cn/problems/walls-and-gates/

題意：給一 m × n 的網格 rooms, 其中每個 cell 有三種可能：

  • 1 表示牆 or 障礙物
  • 0 表示門
  • INF 表示空房間。用 2^31 - 1 = 2147483647 代表 INF。
    且通往門的距離總是小於 2147483647

返回每個空房間位到最近門的距離。如果無法到達門, 則距離設為 INF。

Solution：

想法：利用 BFS（因為可能不只一個門）, 以門為起點向外做 BFS

typedef pair<int, int> pii;

class Solution {
public:
    void wallsAndGates(vector<vector<int>>& rooms) {
        m = rooms.size(), n = rooms[0].size();

        int dist = 1; // 房間離門的最小距離為 1
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (rooms[i][j] == 0) {
                    q.emplace(pii{i, j});
                }
            }
        }

        bfs(rooms, dist);
    }

private:
    int m, n;
    queue<pii> q;
    vector<pii> dirs = {
        {0, 1}, {0, -1},
        {1, 0}, {-1, 0}
    };

    void bfs(vector<vector<int>>& rooms, int& dist){
        while (!q.empty()) {
            for (int k = q.size(); k > 0; --k) {
                const auto [y, x] = q.front();
                q.pop();

                for (const auto& [dirY, dirX] : dirs) {
                    const int r = y + dirY, c = x + dirX;
                    if (!outOfBound(r, c) && rooms[r][c] == INT_MAX) {
                        rooms[r][c] = dist;
                        q.emplace(pii{r, c});
                    }
                }
            }
            ++dist;
        }
    }

    bool outOfBound(const int i, const int j){
        if (i < 0 || i == m || j < 0 || j == n) {
            return true;
        }
        return false;
    }
};
  • space：$O(m \cdot n)$ ➔ 遍歷 rooms
  • space：$O(m \cdot n)$ ➔ q 中元素個數不超過 m * n, worse case：rooms 元素皆為 0