317. Shortest Distance from All Buildings

问题来自 317. Shortest Distance from All Buildings

---

刚看到这道题的时候，觉得和296. Best Meeting Point很像，但是实际上不能用296的思想。因为这次有obstacle，并且“meeting point”不能是building的位置。

这道题得用BFS，但不是BFS每个empty land，而是对每一个grid[r][c]==1的点进行BFS，使用一些技巧，使得后面执行的BFS尽可能的少访问一些点。方法是：

1. bfs第一个building的时候，只bfs那些等于0的点，bfs后将这些点的值设成-1
2. bfs第二个building的时候，只bfs那些等于-1的点，bfs后将这些点的值设成-2
3. bfs第三个building的时候，只bfs那些等于-2的点，bfs后将这些点的值设成-3
4. bfs第四个building的时候，只bfs那些等于-3的点，bfs后将这些点的值设成-4
5. ……….

上面的方法是可行的，因为我们需要找到那些能被所有building访问到的点。下面的代码中用total(一个二维数组)记录了已经访问了的building的shortest distance的和，同时下面的代码在BFS后会返回此次BFS是否成功，如果成功则return true，otherwise false，这样做可以尽早判定这个问题是否有解。

最后就是遍历total数组，找到最小的那个（当然可以在bfs的过程中就记录最小的distance和，不用最后再来一个两层的for循环）。
这道题BFS building而不是BFS empty land倒是和poj 3501 Escape from Enemy Territory里面的第一次BFS有点像。。。。

---

class Solution {
public:
    int shortestDistance(vector<vector<int> >& grid) {
        int row = grid.size();
        if(row == 0) return -1;
        int col = grid[0].size();
        if(col == 0) return -1;
        
        vector<vector<int> > total(row, vector<int>(col, 0));
        int travelled = 0;
        for(int r = 0; r < row; ++r)
            for(int c = 0; c < col; ++c)
                if(grid[r][c] == 1)
                {
                    if(!bfs(grid, r, c, total, travelled))
                        return -1;
                    ++travelled;
                }
        
        int mini = INT_MAX;
        for(int r = 0; r < row; ++r)
            for(int c = 0; c < col; ++c)
                if(grid[r][c] == -travelled && total[r][c] < mini)
                    mini = total[r][c];
        return mini;
    }
private:
    bool bfs(vector<vector<int> > &grid, int r, int c, vector<vector<int> > &total, int travelled)
    {
        int row = grid.size(), col = grid[0].size();
        int dir[][2] = {{-1,0},{1,0},{0,1},{0,-1}};
        
        queue<pair<int, int> > tool;
        tool.push(pair<int, int>(r, c));
        
        bool flag = false;
        int step = 1;
        while(!tool.empty())
        {
            int size = tool.size();
            while(size--)
            {
                pair<int, int> tmp = tool.front(); tool.pop();
                for(int d = 0; d < 4; ++d) 
                { 
                    int tmpr = tmp.first+dir[d][0]; 
                    int tmpc = tmp.second+dir[d][1]; 
                    if(tmpr >= 0 && tmpr < row && tmpc >= 0 && tmpc < col && grid[tmpr][tmpc] == -travelled)
                    {
                        flag = true;
                        grid[tmpr][tmpc] = -travelled-1;
                        tool.push(pair<int, int>(tmpr, tmpc));
                        total[tmpr][tmpc] += step;
                    }
                }
            }
            ++step;
        }
        return flag;
    }
};