题目描述
给你一个 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.lengthn == grid[i].length1 <= m, n <= 50grid[i][j] 是 0, 1 或 2grid 中 至少 有 一幢 建筑
解法
方法一
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 | 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
|
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 | 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;
}
}
|
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 | 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;
}
};
|
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 | 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
}
|