Question

317. 离建筑物最近的距离

English Version

题目描述

给你一个 m × n 的网格，值为 0 、 1 或 2 ，其中:

• 每一个 0 代表一块你可以自由通过的 空地 
• 每一个 1 代表一个你不能通过的 建筑
• 每个 2 标记一个你不能通过的 障碍 

你想要在一块空地上建造一所房子，在 最短的总旅行距离 内到达所有的建筑。你只能上下左右移动。

返回到该房子的 最短旅行距离 。如果根据上述规则无法建造这样的房子，则返回 -1 。

总旅行距离 是朋友们家到聚会地点的距离之和。

使用 曼哈顿距离 计算距离，其中距离 (p1, p2) = |p2.x - p1.x | + | p2.y - p1.y | 。

 

示例  1：

输入：grid = [[1,0,2,0,1],[0,0,0,0,0],[0,0,1,0,0]]
输出：7 
解析：给定三个建筑物 (0,0)、(0,4) 和 (2,2) 以及一个位于 (0,2) 的障碍物。
由于总距离之和 3+3+1=7 最优，所以位置 (1,2) 是符合要求的最优地点。
故返回7。

示例 2:

输入: grid = [[1,0]]
输出: 1

示例 3:

输入: grid = [[1]]
输出: -1

 

提示:

• m == grid.length
• n == grid[i].length
• 1 <= m, n <= 50
• grid[i][j] 是 0, 1 或 2
• grid 中 至少 有 一幢 建筑

解法

方法一

class Solution:
  def shortestDistance(self, grid: List[List[int]]) -> int:
    m, n = len(grid), len(grid[0])
    q = deque()
    total = 0
    cnt = [[0] * n for _ in range(m)]
    dist = [[0] * n for _ in range(m)]
    for i in range(m):
      for j in range(n):
        if grid[i][j] == 1:
          total += 1
          q.append((i, j))
          d = 0
          vis = set()
          while q:
            d += 1
            for _ in range(len(q)):
              r, c = q.popleft()
              for a, b in [[0, 1], [0, -1], [1, 0], [-1, 0]]:
                x, y = r + a, c + b
                if (
                  0 <= x < m
                  and 0 <= y < n
                  and grid[x][y] == 0
                  and (x, y) not in vis
                ):
                  cnt[x][y] += 1
                  dist[x][y] += d
                  q.append((x, y))
                  vis.add((x, y))
    ans = inf
    for i in range(m):
      for j in range(n):
        if grid[i][j] == 0 and cnt[i][j] == total:
          ans = min(ans, dist[i][j])
    return -1 if ans == inf else ans

class Solution {
  public int shortestDistance(int[][] grid) {
    int m = grid.length;
    int n = grid[0].length;
    Deque<int[]> q = new LinkedList<>();
    int total = 0;
    int[][] cnt = new int[m][n];
    int[][] dist = new int[m][n];
    int[] dirs = {-1, 0, 1, 0, -1};
    for (int i = 0; i < m; ++i) {
      for (int j = 0; j < n; ++j) {
        if (grid[i][j] == 1) {
          ++total;
          q.offer(new int[] {i, j});
          int d = 0;
          boolean[][] vis = new boolean[m][n];
          while (!q.isEmpty()) {
            ++d;
            for (int k = q.size(); k > 0; --k) {
              int[] p = q.poll();
              for (int l = 0; l < 4; ++l) {
                int x = p[0] + dirs[l];
                int y = p[1] + dirs[l + 1];
                if (x >= 0 && x < m && y >= 0 && y < n && grid[x][y] == 0
                  && !vis[x][y]) {
                  ++cnt[x][y];
                  dist[x][y] += d;
                  q.offer(new int[] {x, y});
                  vis[x][y] = true;
                }
              }
            }
          }
        }
      }
    }
    int ans = Integer.MAX_VALUE;
    for (int i = 0; i < m; ++i) {
      for (int j = 0; j < n; ++j) {
        if (grid[i][j] == 0 && cnt[i][j] == total) {
          ans = Math.min(ans, dist[i][j]);
        }
      }
    }
    return ans == Integer.MAX_VALUE ? -1 : ans;
  }
}

class Solution {
public:
  int shortestDistance(vector<vector<int>>& grid) {
    int m = grid.size();
    int n = grid[0].size();
    typedef pair<int, int> pii;
    queue<pii> q;
    int total = 0;
    vector<vector<int>> cnt(m, vector<int>(n));
    vector<vector<int>> dist(m, vector<int>(n));
    vector<int> dirs = {-1, 0, 1, 0, -1};
    for (int i = 0; i < m; ++i) {
      for (int j = 0; j < n; ++j) {
        if (grid[i][j] == 1) {
          ++total;
          q.push({i, j});
          vector<vector<bool>> vis(m, vector<bool>(n));
          int d = 0;
          while (!q.empty()) {
            ++d;
            for (int k = q.size(); k > 0; --k) {
              auto p = q.front();
              q.pop();
              for (int l = 0; l < 4; ++l) {
                int x = p.first + dirs[l];
                int y = p.second + dirs[l + 1];
                if (x >= 0 && x < m && y >= 0 && y < n && grid[x][y] == 0 && !vis[x][y]) {
                  ++cnt[x][y];
                  dist[x][y] += d;
                  q.push({x, y});
                  vis[x][y] = true;
                }
              }
            }
          }
        }
      }
    }
    int ans = INT_MAX;
    for (int i = 0; i < m; ++i)
      for (int j = 0; j < n; ++j)
        if (grid[i][j] == 0 && cnt[i][j] == total)
          ans = min(ans, dist[i][j]);
    return ans == INT_MAX ? -1 : ans;
  }
};

func shortestDistance(grid [][]int) int {
  m, n := len(grid), len(grid[0])
  var q [][]int
  total := 0
  cnt := make([][]int, m)
  dist := make([][]int, m)
  for i := range cnt {
    cnt[i] = make([]int, n)
    dist[i] = make([]int, n)
  }
  dirs := []int{-1, 0, 1, 0, -1}
  for i := 0; i < m; i++ {
    for j := 0; j < n; j++ {
      if grid[i][j] == 1 {
        total++
        q = append(q, []int{i, j})
        vis := make([]bool, m*n)
        d := 0
        for len(q) > 0 {
          d++
          for k := len(q); k > 0; k-- {
            p := q[0]
            q = q[1:]
            for l := 0; l < 4; l++ {
              x, y := p[0]+dirs[l], p[1]+dirs[l+1]
              if x >= 0 && x < m && y >= 0 && y < n && grid[x][y] == 0 && !vis[x*n+y] {
                cnt[x][y]++
                dist[x][y] += d
                q = append(q, []int{x, y})
                vis[x*n+y] = true
              }
            }
          }
        }
      }
    }
  }

  ans := math.MaxInt32
  for i := 0; i < m; i++ {
    for j := 0; j < n; j++ {
      if grid[i][j] == 0 && cnt[i][j] == total {
        if ans > dist[i][j] {
          ans = dist[i][j]
        }
      }
    }
  }
  if ans == math.MaxInt32 {
    return -1
  }
  return ans
}