317. Shortest Distance from All Buildings - cocoder39/coco39_LC GitHub Wiki
317. Shortest Distance from All Buildings
notes 2024:
- shortest distance in unweighted graph -> bfs
- using visited set to avoid revisiting a node since each node gets its shortest distance upon the first accessing of it
- usually there are less buildings than empty spaces so we'd start BFS from each building
- Maintain a distance matrix where distance[i][j] is the sum of distances from all buildings to the cell (i, j).
- maintain a reach matrix where reach[i][j] counts how many buildings can reach the cell (i, j).
Time Complexity: O(B * m * n) • This is because we perform BFS from each of the B buildings, and each BFS operation can traverse all m \times n cells in the grid. • Space Complexity: O(m * n) • This accounts for the BFS queue, visited matrix, and the distance and reach matrices, all of which are proportional to the number of cells in the grid.
class Solution:
def shortestDistance(self, grid: List[List[int]]) -> int:
if not grid or not grid[0]:
return -1
m, n = len(grid), len(grid[0])
building_num = 0
for i in range(m):
for j in range(n):
if grid[i][j] == 1:
building_num += 1
dist = [[0] * n for _ in range(m)]
reach = [[0] * n for _ in range(m)]
for i in range(m):
for j in range(n):
if grid[i][j] == 1:
self.bfs(grid, dist, reach, i, j)
res = float('inf')
for i in range(m):
for j in range(n):
if grid[i][j] == 0 and reach[i][j] == building_num:
res = min(res, dist[i][j])
return res if res != float('inf') else -1
def bfs(self, grid, dist, reach, row, col):
m, n = len(grid), len(grid[0])
visited = [[False] * n for _ in range(m)]
visited[row][col] = True
queue = collections.deque([(row, col, 0)])
while queue:
cur_row, cur_col, d = queue.popleft()
for dr, dc in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
new_row, new_col = cur_row + dr, cur_col + dc
if 0 <= new_row < m and 0 <= new_col < n:
if not visited[new_row][new_col] and grid[new_row][new_col] == 0:
visited[new_row][new_col] = True
reach[new_row][new_col] += 1
dist[new_row][new_col] += d+1
queue.append((new_row, new_col, d+1))
For each empty slot, applying BFS to get shortest distance from each building to it. T = O(E* M * N) where E is number of empty slots.
An alternative option is to apply bsf for each building instead. T = O(BMN) where B is number of buildings. With this approach, we can apply pruning strategy: during a Bfs if we find that we are unable to get to all buildings, then it means those buildings are not completely connected (i.e, there is no path you can start from one building and get to every else building.), then we can immediately return -1 as result.
class Solution:
def shortestDistance(self, grid: List[List[int]]) -> int:
m, n = len(grid), len(grid[0])
startPoints = []
buildingCount = 0
for i in range(m):
for j in range(n):
if grid[i][j] == 0:
startPoints.append([i, j])
elif grid[i][j] == 1:
buildingCount += 1
res = -1
for x, y in startPoints:
dist = self.getDistance(grid, x, y, buildingCount)
if dist != -1:
if res == -1:
res = dist
else:
res = min(res, dist)
return res
def getDistance(self, grid, startX, startY, buildingCount) -> int:
DIRS = [(-1, 0), (1, 0), (0, -1), (0, 1)]
m, n = len(grid), len(grid[0])
totalDistance = 0
visited = [[False] * n for _ in range(m)]
queue = collections.deque()
queue.append([startX, startY, 0])
visited[startX][startY] = True
while queue:
x, y, distance = queue.popleft()
for dx, dy in DIRS:
nx, ny = x+dx, y+dy
if 0 <= nx < m and 0 <= ny < n:
if grid[nx][ny] != 2 and not visited[nx][ny]:
visited[nx][ny] = True
if grid[nx][ny] == 1:
totalDistance += distance + 1
buildingCount -= 1
if buildingCount == 0:
return totalDistance
continue
queue.append([nx, ny, distance+1])
return -1
==================================================
Main idea:
for each building //O(m * n)
bfs + queue to increase the distance level by level //O(m * n)
time is O(m^2 * n^2)
tips:
instead of using a fresh vector<vector<bool>> visited to mark the empty that has been visited by current bfs, we use a threshold. Initially threshold == 0 and bfs would only visit bins whose grids are 0. Once current bfs finishes, threshold would decrease by 1 for next bfs. Second bfs would only visit bins whose grids are -1 because only those empties can be visited by both first building and second building. So on so forth.
int shortestDistance(vector<vector<int>>& grid) {
int m = grid.size();
if (m == 0)
return -1;
int n = grid[0].size();
vector<vector<int>> dists(m, vector<int>(n)); //dists[i][j] is the total distance from grid[i][j] to all other buildings
vector<vector<int>> dirs{{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
int threshold = 0; // used to update grid, so that gird[i][j] = -i iff it is the ith time to visit it
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (grid[i][j] == 1) {
queue<pair<int, int>> q;
q.push({i, j});
int inc = 1;
while (! q.empty()) {
int sz = q.size();
for (int k = 0; k < sz; k++) { //level by level
auto pos = q.front();
q.pop();
for (auto dir : dirs) {
int row = pos.first + dir[0];
int col = pos.second + dir[1];
if (row >= 0 && row < m && col >= 0 && col < n && grid[row][col] == threshold) {
grid[row][col] = threshold - 1;
dists[row][col] += inc;
q.push({row, col});
// cout << "(" << row << ", " << col << ") :" << grid[row][col] << " "<< dists[row][col] << endl;
}
}
}
inc++;
}
threshold--;
}
}
}
int res = INT_MAX;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (grid[i][j] <= 0 && grid[i][j] == threshold) //that can reach all buildings
res = min(res, dists[i][j]);
}
}
return res == INT_MAX ? -1 : res;
}