317. Shortest Distance from All Buildings

O(m*n*b) time O(m*n) space
思路很直白 遍历每个房子 对每个房子bfs 累加每个空地到每个房子的距离 要找的是一个可以reach所有房子的空地（前提是房子少空地多，否则就要对每个空地bfs）
这道题最重要的corner case是有的房子reach不到所有的空地
下面这个方法比较tricky但是省空间且不需要最后的遍历

class Solution {
public:
    int shortestDistance(vector<vector<int>>& grid) {
        if (grid.empty() || grid[0].empty()) return -1;
        int m = grid.size(), n = grid[0].size();
        vector<vector<int>> s(m, vector<int>(n));
        int cnt = 0, res = INT_MAX;
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (grid[i][j] == 1) {
                    res = bfs(s, grid, cnt--, i, j, m, n); // cnt其实就是房子的个数
                    if (res == INT_MAX) return -1; // 有任何一个房子不能reach到所有空地，直接返回-1
                }
            }
        }
        return res;
    }

    int bfs(vector<vector<int>> &s, vector<vector<int>> &grid, int cnt, int i, int j, int m, int n) {
        queue<pair<int, int>> q;
        q.emplace(i, j);
        int d = 1, res = INT_MAX;
        while (!q.empty()) {
            for (int k = q.size(); k > 0; --k) {
                auto [ui, uj] = q.front(); q.pop();
                for (int p = 0; p < 4; ++p) {
                    int vi = ui + di[p];
                    int vj = uj + dj[p];
                    if (0 <= vi && vi < m && 0 <= vj && vj < n && cnt == grid[vi][vj]) { // 只有当前空地的计数器等于之前遍历过的所有房子的个数才有可能对res进行更新，如果之前有某个房子不能reach到，则当前空地的计数器一定和cnt不等；如果当前房子是reach不到的则res也不会更新，因为res会被overwritten，所以如果有一个房子reach不到，那么res会被改成INT_MAX并且之后再遍历的所有房子都不会再更新res
                        grid[vi][vj] = cnt - 1;
                        s[vi][vj] += d;
                        q.emplace(vi, vj);
                        res = min(res, s[vi][vj]);
                    }
                }
            }
            ++d;
        }
        return res;
    }

    int di[4] = {1, -1, 0, 0}, dj[4] = {0, 0, 1, -1};
};

class Solution {
public:
    int shortestDistance(vector<vector<int>>& grid) {
        if (grid.empty() || grid[0].empty()) return -1;
        int m = grid.size(), n = grid[0].size();
        vector<vector<int>> s(m, vector<int>(n)), cnt = s; // s用来累加每个空地到其他房子的距离，cnt用来统计每个空地能有多少个房子reach
        int color = 0; // color用来给grid里的空地着色，避免重复访问
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (grid[i][j] == 1) {
                    bfs(s, grid, cnt, --color, i, j, m, n);
                }
            }
        }
        int res = INT_MAX;
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (s[i][j] > 0 && cnt[i][j] + color == 0) { // 如果存在一个空地可以reach所有房子，s[i][j] > 0说明是空地，cnt[i][j] + color == 0说明可以reach所有房子
                    res = min(res, s[i][j]);
                }
            }
        }
        return res == INT_MAX ? -1 : res; // 如果不存在能reach所有房子的空地
    }

    void bfs(vector<vector<int>> &s, vector<vector<int>> &grid, vector<vector<int>> &cnt, int color, int i, int j, int m, int n) {
        queue<pair<int, int>> q;
        q.emplace(i, j);
        int d = 1;
        while (!q.empty()) {
            for (int k = q.size(); k > 0; --k) {
                auto u = q.front(); q.pop();
                for (int p = 0; p < 4; ++p) {
                    int vi = u.first + di[p];
                    int vj = u.second + dj[p];
                    if (0 <= vi && vi < m && 0 <= vj && vj < n && color < grid[vi][vj] && grid[vi][vj] < 1) {
                        grid[vi][vj] = color;
                        s[vi][vj] += d;
                        q.emplace(vi, vj);
                        ++cnt[vi][vj];
                    }
                }
            }
            ++d;
        }
    }

    int di[4] = {1, -1, 0, 0}, dj[4] = {0, 0, 1, -1};
};