317. Shortest Distance from All Buildings

I followed the top rated solution. We scan from each building and calculate the distance from every 0 to itself. This can be done by BFS. In the end, we'll get a cumulative distance matrix, i.e. distance[2][3] is the sum of distances from all reachable buildings to grid[2][3] (grid[2][3] must be 0). Take the example in the problem, the eventual distance matrix will be:

 x  - 9 - x - 9 -  x
 9  - 8 - 7 - 8 -  9
10 - 9 - x - 9 - 10

So it'll be easy to figure out that the minimum distance is 7. However, this is just not enough to get a right answer. I mentioned "reachable" buildings. Why I emphasize "reachable"? Let's see an example.

1 - 0 - 0 - 0 - 1                                                         x - 7 - 6 - 5 - x
0 - 2 - 0 - 2 - 0    we can get distance matrix as      1 - x - 7 - x - 1
2 - 0 - 1 - 0 - 2                                                         x - 1 - x - 1 - x

If we only return the minimum distance, we'll be wrong in this case because we can't reach all the buildings in some place. To solve it, we need to have another map to count the reachable buildings for each position. And when we check the distance, we need to make sure that place has the reachable buildings equal to total buildings.

1:  class Solution {  
2:  public:  
3:    int shortestDistance(vector<vector<int>>& grid) {  
4:      int row = grid.size();  
5:      if (row == 0) return 0;  
6:      int col = grid[0].size();  
7:      vector<pair<int, int>> dir = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};  
8:      vector<vector<int>> distances(row, vector<int>(col, 0));  
9:      vector<vector<int>> reach(row, vector<int>(col, 0));  
10:      int buildings = 0;  
11:      for (int i = 0; i < row; i++) {  
12:        for (int j = 0; j < col; j++) {  
13:          if (grid[i][j] == 1) {  
14:            int dist = 0;  
15:            buildings++;  
16:            queue<pair<int,int>> curQue, nextQue;  
17:            vector<vector<bool>> visited(row, vector<bool>(col, 0));  
18:            curQue.push(make_pair(i, j));  
19:            while (!curQue.empty()) {  
20:              dist++;  
21:              while(!curQue.empty()) {  
22:                pair<int,int> cur = curQue.front();  
23:                curQue.pop();  
24:                reach[cur.first][cur.second]++;  
25:                for (int k = 0; k < dir.size(); k++) {  
26:                  int ii = cur.first + dir[k].first;  
27:                  int jj = cur.second + dir[k].second;  
28:                  if (ii >= 0 && ii < row && jj >= 0 && jj < col && !visited[ii][jj] && grid[ii][jj] == 0) {  
29:                    nextQue.push(make_pair(ii, jj));  
30:                    distances[ii][jj] += dist;  
31:                    visited[ii][jj] = true;  
32:                  }  
33:                }  
34:              }  
35:              swap(curQue, nextQue);  
36:            }  
37:          }  
38:        }  
39:      }  
40:      int res = INT_MAX;  
41:      for (int i = 0; i < row; i++) {  
42:        for (int j = 0; j < col; j++) {  
43:          if (grid[i][j] == 0 && reach[i][j] == buildings)  
44:            res = min(res, distances[i][j]);  
45:        }  
46:      }  
47:      return res == INT_MAX ? -1 : res;  
48:    }  
49:  };  

When I revisited this problem, I used a concept of local distance and global distance which seems to be easier to understand.

1:  class Solution {  
2:  public:  
3:    int shortestDistance(vector<vector<int>>& grid) {  
4:      int rows = grid.size();  
5:      if (rows == 0) return -1;  
6:      int cols = grid[0].size();  
7:      queue<pair<int,int>> q;  
8:      vector<vector<int>> global_dist(rows, vector<int>(cols, 0));  
9:      vector<vector<int>> reachable(rows, vector<int>(cols, 0));  
10:      vector<pair<int, int>> dir = {{1,0}, {-1,0}, {0,1}, {0,-1}};  
11:      int buildings = 0;  
12:      for (int i = 0; i < rows; i++) {  
13:        for (int j = 0; j < cols; j++) {  
14:          if (grid[i][j] == 1) {  
15:            buildings++;  
16:            q.push(make_pair(i, j));  
17:            vector<vector<int>> local_dist(rows, vector<int>(cols, 0));  
18:            while (!q.empty()) {  
19:              int sz = q.size();  
20:              for (int k = 0; k < sz; k++) {  
21:                int x = q.front().first;  
22:                int y = q.front().second;  
23:                q.pop();  
24:                for (int d = 0; d < dir.size(); d++) {  
25:                  int xx = x + dir[d].first;  
26:                  int yy = y + dir[d].second;  
27:                  if (xx<0||xx==rows||yy<0||yy==cols||grid[xx][yy]!=0||local_dist[xx][yy]!=0) continue;  
28:                  local_dist[xx][yy] = local_dist[x][y] + 1;  
29:                  global_dist[xx][yy] += local_dist[xx][yy];  
30:                  reachable[xx][yy]++;  
31:                  q.push(make_pair(xx, yy));  
32:                }  
33:              }  
34:            }  
35:          }  
36:        }  
37:      }  
38:      int minDist = INT_MAX;  
39:      for (int i = 0; i < rows; i++) {  
40:        for (int j = 0; j < cols; j++) {  
41:          if (grid[i][j] == 0 && reachable[i][j] == buildings) {  
42:            minDist = min(minDist, global_dist[i][j]);  
43:          }  
44:        }  
45:      }  
46:      return minDist == INT_MAX ? -1 : minDist;  
47:    }  
48:  };