-
Notifications
You must be signed in to change notification settings - Fork 28
/
Shortest_Distance_from_All_Buildings.cpp
67 lines (58 loc) · 2.29 KB
/
Shortest_Distance_from_All_Buildings.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
class Solution {
const int dx[4] = {0, -1, 0, 1};
const int dy[4] = {-1, 0, 1, 0};
inline bool isValid(int x, int y, vector<vector<int>> const& grid, vector<vector<bool>> const& visited) const {
return (x >= 0 and y >= 0 and x < (int)grid.size() and y < (int)grid[0].size() and !visited[x][y] and !grid[x][y]);
}
void bfs(int x, int y, vector<vector<int>> const& grid, vector<vector<int>>& dist, vector<vector<int>>& cnt) {
int m = (int)grid.size(), n = (int)grid[0].size();
vector<vector<bool>> visited(m, vector<bool>(n, false));
vector<pair<int, int>> prevLevel{{x, y}}, currLevel;
visited[x][y] = true;
int depth = 0;
while(!prevLevel.empty()) {
++depth;
currLevel.clear();
for(int i = 0; i < (int)prevLevel.size(); ++i) {
int x = prevLevel[i].first, y = prevLevel[i].second;
for(int k = 0; k < 4; ++k) {
int newX = x + dx[k], newY = y + dy[k];
if(isValid(newX, newY, grid, visited)) {
visited[newX][newY] = true;
dist[newX][newY] += depth;
++cnt[newX][newY];
currLevel.push_back({newX, newY});
}
}
}
swap(prevLevel, currLevel);
}
}
public:
int shortestDistance(vector<vector<int>>& grid) {
int m = (int)grid.size();
if(m == 0) return 0;
int n = (int)grid[0].size();
if(n == 0) return 0;
vector<vector<int>> dist(m, vector<int>(n, 0));
vector<vector<int>> cnt(m, vector<int>(n, 0));
int buildings = 0;
for(int i = 0; i < m; ++i) {
for(int j = 0; j < n; ++j) {
if(grid[i][j] == 1) {
buildings++;
bfs(i, j, grid, dist, cnt);
}
}
}
int result = INT_MAX;
for(int i = 0; i < m; ++i) {
for(int j = 0; j < n; ++j) {
if(cnt[i][j] == buildings and dist[i][j] < result) {
result = dist[i][j];
}
}
}
return ((result != INT_MAX) ? result : -1);
}
};