Skip to content

317. Shortest Distance from All Buildings 👍

  • Time: $O(m^2n^2)$
  • Space: $O(mn)$
 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 {
 public:
  int shortestDistance(vector<vector<int>>& grid) {
    constexpr int dirs[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
    const int m = grid.size();
    const int n = grid[0].size();
    const int nBuildings = getBuildingsCount(grid);
    int ans = INT_MAX;
    // dist[i][j] := the total distance of grid[i][j] (0) to reach all the
    // buildings (1)
    vector<vector<int>> dist(m, vector<int>(n));
    // reachCount[i][j] := the number of buildings (1) grid[i][j] (0) can reach
    vector<vector<int>> reachCount(m, vector<int>(n));

    auto bfs = [&](int row, int col) -> bool {
      queue<pair<int, int>> q{{{row, col}}};
      vector<vector<bool>> seen(m, vector<bool>(n));
      seen[row][col] = true;
      int seenBuildings = 1;

      for (int step = 1; !q.empty(); ++step)
        for (int sz = q.size(); sz > 0; --sz) {
          const auto [i, j] = q.front();
          q.pop();
          for (const auto& [dx, dy] : dirs) {
            const int x = i + dx;
            const int y = j + dy;
            if (x < 0 || x == m || y < 0 || y == n)
              continue;
            if (seen[x][y])
              continue;
            seen[x][y] = true;
            if (!grid[x][y]) {
              dist[x][y] += step;
              ++reachCount[x][y];
              q.emplace(x, y);
            } else if (grid[x][y] == 1) {
              ++seenBuildings;
            }
          }
        }

      return seenBuildings == nBuildings;
    };

    for (int i = 0; i < m; ++i)
      for (int j = 0; j < n; ++j)
        if (grid[i][j] == 1)  // BFS from this building.
          if (!bfs(i, j))
            return -1;

    for (int i = 0; i < m; ++i)
      for (int j = 0; j < n; ++j)
        if (reachCount[i][j] == nBuildings)
          ans = min(ans, dist[i][j]);

    return ans == INT_MAX ? -1 : ans;
  }

 private:
  int getBuildingsCount(vector<vector<int>>& grid) {
    return accumulate(grid.begin(), grid.end(), 0,
                      [](int subtotal, vector<int>& row) {
      return subtotal + ranges::count(row, 1);
    });
  }
};

 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
68
69
70
71
class Solution {
  public int shortestDistance(int[][] grid) {
    final int m = grid.length;
    final int n = grid[0].length;
    final int nBuildings = getBuildingsCount(grid);
    int ans = Integer.MAX_VALUE;
    // dist[i][j] := the total distance of grid[i][j] (0) to reach all the
    // buildings (1)
    int[][] dist = new int[m][n];
    // reachCount[i][j] := the number of buildings (1) grid[i][j] (0) can reach
    int[][] reachCount = new int[m][n];

    for (int i = 0; i < m; ++i)
      for (int j = 0; j < n; ++j)
        if (grid[i][j] == 1) // BFS from this building.
          if (!bfs(grid, i, j, dist, reachCount, nBuildings))
            return -1;

    for (int i = 0; i < m; ++i)
      for (int j = 0; j < n; ++j)
        if (reachCount[i][j] == nBuildings)
          ans = Math.min(ans, dist[i][j]);

    return ans == Integer.MAX_VALUE ? -1 : ans;
  }

  private static final int[][] dirs = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};

  private boolean bfs(int[][] grid, int row, int col, int[][] dist, int[][] reachCount,
                      int nBuildings) {
    final int m = grid.length;
    final int n = grid[0].length;
    Queue<Pair<Integer, Integer>> q = new ArrayDeque<>(List.of(new Pair<>(row, col)));
    boolean[][] seen = new boolean[m][n];
    seen[row][col] = true;
    int seenBuildings = 1;

    for (int step = 1; !q.isEmpty(); ++step)
      for (int sz = q.size(); sz > 0; --sz) {
        final int i = q.peek().getKey();
        final int j = q.poll().getValue();
        for (int[] dir : dirs) {
          final int x = i + dir[0];
          final int y = j + dir[1];
          if (x < 0 || x == m || y < 0 || y == n)
            continue;
          if (seen[x][y])
            continue;
          seen[x][y] = true;
          if (grid[x][y] == 0) {
            dist[x][y] += step;
            ++reachCount[x][y];
            q.offer(new Pair<>(x, y));
          } else if (grid[x][y] == 1) {
            ++seenBuildings;
          }
        }
      }

    return seenBuildings == nBuildings;
  }

  private int getBuildingsCount(int[][] grid) {
    int buildingCount = 0;
    for (int[] row : grid)
      for (final int cell : row)
        if (cell == 1)
          ++buildingCount;
    return buildingCount;
  }
}

 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
class Solution:
  def shortestDistance(self, grid: list[list[int]]) -> int:
    dirs = ((0, 1), (1, 0), (0, -1), (-1, 0))
    m = len(grid)
    n = len(grid[0])
    nBuildings = sum(a == 1 for row in grid for a in row)
    ans = math.inf
    # dist[i][j] := the total distance of grid[i][j] (0) to reach all the
    # buildings (1)
    dist = [[0] * n for _ in range(m)]
    # reachCount[i][j] := the number of buildings (1) grid[i][j] (0) can reach
    reachCount = [[0] * n for _ in range(m)]

    def bfs(row: int, col: int) -> bool:
      q = collections.deque([(row, col)])
      seen = {(row, col)}
      seenBuildings = 1

      step = 1
      while q:
        for _ in range(len(q)):
          i, j = q.popleft()
          for dx, dy in dirs:
            x = i + dx
            y = j + dy
            if x < 0 or x == m or y < 0 or y == n:
              continue
            if (x, y) in seen:
              continue
            seen.add((x, y))
            if not grid[x][y]:
              dist[x][y] += step
              reachCount[x][y] += 1
              q.append((x, y))
            elif grid[x][y] == 1:
              seenBuildings += 1
        step += 1

      # True if all the buildings (1) are connected
      return seenBuildings == nBuildings

    for i in range(m):
      for j in range(n):
        if grid[i][j] == 1:  # BFS from this building.
          if not bfs(i, j):
            return -1

    for i in range(m):
      for j in range(n):
        if reachCount[i][j] == nBuildings:
          ans = min(ans, dist[i][j])

    return -1 if ans == math.inf else ans