LeetCode Solutions

			

class Solution {
 public:
  int shortestDistance(vector<vector<int>>& grid) {
    const int m = grid.size();
    const int n = grid[0].size();
    const int nBuildings = getBuildingCount(grid);
    const vector<int> dirs{0, 1, 0, -1, 0};
    int ans = INT_MAX;
    // dist[i][j] := total distance of grid[i][j] (0) to reach all buildings (1)
    vector<vector<int>> dist(m, vector<int>(n));
    // reachCount[i][j] := # 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 depth = 0;
      int seenBuildings = 1;

      while (!q.empty()) {
        ++depth;
        for (int sz = q.size(); sz > 0; --sz) {
          const auto [i, j] = q.front();
          q.pop();
          for (int k = 0; k < 4; ++k) {
            const int x = i + dirs[k];
            const int y = j + dirs[k + 1];
            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] += depth;
              ++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 getBuildingCount(vector<vector<int>>& grid) {
    return accumulate(begin(grid), end(grid), 0, [](int s, vector<int>& row) {
      return s + count(begin(row), end(row), 1);
    });
  }
};

			

class Solution {
  public int shortestDistance(int[][] grid) {
    final int m = grid.length;
    final int n = grid[0].length;
    final int nBuildings = getBuildingCount(grid);
    int ans = Integer.MAX_VALUE;
    // dist[i][j] := total distance of grid[i][j] (0) to reach all buildings (1)
    int[][] dist = new int[m][n];
    // reachCount[i][j] := # 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, 0, -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<int[]> q = new ArrayDeque<>(Arrays.asList(new int[] {row, col}));
    boolean[][] seen = new boolean[m][n];
    seen[row][col] = true;
    int depth = 0;
    int seenBuildings = 1;

    while (!q.isEmpty()) {
      ++depth;
      for (int sz = q.size(); sz > 0; --sz) {
        final int i = q.peek()[0];
        final int j = q.poll()[1];
        for (int k = 0; k < 4; ++k) {
          final int x = i + dirs[k];
          final int y = j + dirs[k + 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] += depth;
            ++reachCount[x][y];
            q.offer(new int[] {x, y});
          } else if (grid[x][y] == 1) {
            ++seenBuildings;
          }
        }
      }
    }

    return seenBuildings == nBuildings;
  }

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

			

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

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

      while q:
        depth += 1
        for _ in range(len(q)):
          i, j = q.popleft()
          for k in range(4):
            x = i + dirs[k]
            y = j + dirs[k + 1]
            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] += depth
              reachCount[x][y] += 1
              q.append((x, y))
            elif grid[x][y] == 1:
              seenBuildings += 1

      # True if all 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