You want to build a house on an empty land which reaches all buildings in the shortest amount of distance. You can only move up, down, left and right. You are given a 2D grid of values 0, 1 or 2, where:
Each 0 marks an empty land which you can pass by freely.
Each 1 marks a building which you cannot pass through.
Each 2 marks an obstacle which you cannot pass through.
Example:
Input: [[1,0,2,0,1],[0,0,0,0,0],[0,0,1,0,0]]
1 - 0 - 2 - 0 - 1
| | | | |
0 - 0 - 0 - 0 - 0
| | | | |
0 - 0 - 1 - 0 - 0
Output: 7
Explanation: Given three buildings at (0,0), (0,4), (2,2), and an obstacle at (0,2),
the point (1,2) is an ideal empty land to build a house, as the total
travel distance of 3+3+1=7 is minimal. So return 7.
Note:
There will be at least one building. If it is not possible to build such house according to the above rules, return -1.
// BFS
int shortestDistance(vector<vector<int>>& grid) { // time: O(m^2 * n^2); space: O(m * n)
int res = numeric_limits<int>::max(), search_val = 0, m = grid.size(), n = grid[0].size();
// vector<vector<int> > sums = grid;
vector<vector<int> > sums(m, vector<int> (n, 0));
vector<vector<int> > dirs({{-1, 0}, {1, 0}, {0, -1}, {0, 1}});
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
// Start from each building
if (grid[i][j] == 1) {
res = numeric_limits<int>::max();
// vector<vector<int> > dist = grid; // distance map
vector<vector<int> > dist(m, vector<int> (n, 0));
queue<pair<int, int> > q({{i, j}});
// BFS
while (!q.empty()) {
auto t = q.front(); q.pop();
for (const vector<int>& dir : dirs) {
int x = t.first + dir[0], y = t.second + dir[1];
if (x >= 0 && x < m && y >= 0 && y < n && grid[x][y] == search_val) {
--grid[x][y]; // similar to mark as visited
dist[x][y] = dist[t.first][t.second] + 1;
// sums[x][y] += dist[x][y] - 1; // building is 1 in the very beginning
sums[x][y] += dist[x][y];
q.push({x, y});
res = min(res, sums[x][y]);
}
}
}
--search_val;
}
}
}
return res != numeric_limits<int>::max() ? res : -1;
}
// BFS
int shortestDistance(vector<vector<int>>& grid) { // time: O(m^2 * n^2); space: O(m * n)
int res = numeric_limits<int>::max(), buildingCnt = 0, m = grid.size(), n = grid[0].size();
// sums: accumulated distance for each grid to reachable buildings
// cnt: total number of buildings reachable from each grid
vector<vector<int> > sums(m, vector<int> (n, 0)), cnt = sums;
vector<vector<int> > dirs({{-1, 0}, {1, 0}, {0, -1}, {0, 1}});
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
if (grid[i][j] == 1) {
++buildingCnt;
queue<pair<int, int> > q({{i, j}});
vector<vector<bool> > visited(m, vector<bool> (n, false));
int level = 1;
while (!q.empty()) {
int size = q.size();
for (int i = 0; i < size; ++i) {
auto t = q.front(); q.pop();
for (const vector<int>& dir : dirs) {
int x = t.first + dir[0], y = t.second + dir[1];
if (x >= 0 && x < m && y >= 0 && y < n && grid[x][y] == 0 && !visited[x][y]) {
sums[x][y] += level;
++cnt[x][y];
visited[x][y] = true;
q.push({x, y});
}
}
}
++level;
}
}
}
}
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
if (grid[i][j] == 0 && cnt[i][j] == buildingCnt) {
res = min(res, sums[i][j]);
}
}
}
return res == numeric_limits<int>::max() ? -1 : res;
}