317. Shortest Distance from All Buildings

由0，1，2组成的二维矩阵，0代表能通过，1和2代表不能通过，让选取一个0的位置，使得它到所有1的距离最短。最短距离而且又是『显式』图，用BFS。问0->1最短，要从1->0做BFS，有两个原因: 1. 一般1的数目要<<0，所需处理的结点更少；2. 如果是只找一个最近的1，从所有的1开始一起遍历，每次遇到的没被标记过的0一定是被最近的1（之一）访问着，这个0就可以被标记以后无需再访问。这道题要求找全局最近，不能用统一的visited做标记，第二个优点不适用，但1->0做BFS也一般更好。因此对每个1开始一个新的BFS，用一个global的dist和cnt分别记录(x, y)和其它1的总距离和能访问到几个1。

题目和解法参考了这。

class Solution {
public:
    /**
     * @param grid: the 2D grid
     * @return: the shortest distance
     */
    int shortestDistance(vector<vector<int>> &grid) {
        int res = INT_MAX, buildings = 0, M = grid.size(), N = grid[0].size();
        // 记录(x, y)和其它1的总距离和能访问到几个1
        vector<vector<int>> dist(M, vector<int>(N, 0)), cnt(dist); 
        vector<vector<int>> dirs{{0, -1}, {0, 1}, {-1, 0}, {1, 0}};
        for (int i = 0; i < M; ++i) {
            for (int j = 0; j < N; ++j) {
                if (grid[i][j] == 1) {
                    ++buildings;
                    queue<vector<int>> q;
                    q.push({i, j});
                    vector<vector<bool>> visited(M, vector<bool>(N, false));
                    int level = 1;
                    while (!q.empty()) {
                        for (int k = q.size() - 1; k >= 0; --k) {
                            const auto &t = q.front(); 
                            for (const auto &d : dirs) {
                                const int x = t[0] + d[0], y = t[1] + d[1];
                                if (x >= 0 && x < M && y >= 0 && y < N && grid[x][y] == 0 && !visited[x][y]) {
                                    dist[x][y] += level;
                                    ++cnt[x][y];
                                    visited[x][y] = true;
                                    q.push({x, y});
                                }
                            }
                            q.pop();
                        }
                        ++level;
                    }
                }
            }
        }
        for (int i = 0; i < M; ++i) {
            for (int j = 0; j < N; ++j) {
                if (grid[i][j] == 0 && cnt[i][j] == buildings) {
                    res = min(res, dist[i][j]);
                }
            }
        }
        return res == INT_MAX ? -1 : res;
    }
};