数据结构
网络
关系型数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法律研究C++ 中所有建筑物的最短距离
假设我们想在一块空地上建一座房子，这座房子到所有建筑物的距离都最短。我们只能向四个方向移动，例如上、下、左和右。我们有一个 2D 网格，其值为 0、1 或 2，其中 -
0 表示我们可以自由通过的空地。
1 表示我们无法穿过的建筑物。
2 表示我们无法穿过的障碍物。
因此，如果输入类似于
| 1 | 0 | 2 | 0 | 1 |
| 0 | 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 0 | 0 |
那么输出将为 7，因为存在三个建筑物，分别位于 (0,0)、(0,4)、(2,2)，并且在 (0,2) 处有一个障碍物，所以 (1,2) 是建造房子的理想空地，因为总旅行距离 3+3+1=7 最小。
为了解决这个问题，我们将遵循以下步骤 -
ret := inf
n := 网格的行大小
m := 网格的列大小
numberOfOnes := 0
定义一个大小为 n x m 的二维数组 dist
定义一个大小为 n x m 的二维数组 reach
对于初始化 i := 0，当 i < n 时，更新（i 增加 1），执行 -
对于初始化 j := 0，当 j < m 时，更新（j 增加 1），执行 -
如果 grid[i, j] 与 1 相同，则 -
（numberOfOnes 增加 1）
定义一个队列 q
将 {i, j} 插入到 q 中
定义一个集合 visited
对于初始化 lvl := 1，当 q 不为空时，更新（lvl 增加 1），执行 -
sz := q 的大小
当 sz 不为零时，在每次迭代中减少 sz，执行 -
curr := q 的第一个元素
从 q 中删除元素
x := curr.first
y := curr.second
对于初始化 k := 0，当 k < 4 时，更新（k 增加 1），执行 -
nx := x + dir[k, 0]
ny := y + dir[k, 1]
如果 nx 和 ny 在网格范围内或 grid[nx,ny] 不为 0，则
忽略以下部分，跳到下一轮迭代
将 {nx, ny} 插入到 visited 中
dist[nx, ny] := dist[nx, ny] + lvl
（reach[nx, ny] 增加 1）
将 {nx, ny} 插入到 q 中
对于初始化 i := 0，当 i < n 时，更新（i 增加 1），执行 -
对于初始化 j := 0，当 j < m 时，更新（j 增加 1），执行 -
如果 grid[i, j] 与 0 相同且 reach[i, j] 与 numberOfOnes 相同，则 -
ret := ret 和 dist[i, j] 的最小值
返回（如果 ret 与 inf 相同，则为 -1，否则为 ret）
示例
让我们看看以下实现以更好地理解 -
int dir[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
class Solution {
public:
int shortestDistance(vector<vector<int>>& grid) {
int ret = INT_MAX;
int n = grid.size();
int m = grid[0].size();
int numberOfOnes = 0;
vector < vector <int> > dist(n, vector <int>(m));
vector < vector <int> > reach(n, vector <int>(m));
for(int i = 0; i < n; i++){
for(int j = 0; j < m; j++){
if(grid[i][j] == 1){
numberOfOnes++;
queue < pair <int, int> > q;
q.push({i, j});
set < pair <int, int> > visited;
for(int lvl = 1; !q.empty(); lvl++){
int sz = q.size();
while(sz--){
pair <int, int> curr = q.front();
q.pop();
int x = curr.first;
int y = curr.second;
for(int k = 0; k < 4; k++){
int nx = x + dir[k][0];
int ny = y + dir[k][1];
if(nx < 0 || ny < 0 || nx >= n || ny >= m || visited.count({nx, ny}) || grid[nx][ny] != 0) continue;
visited.insert({nx, ny});
dist[nx][ny] += lvl;
reach[nx][ny]++;
q.push({nx, ny});
}
}
}
}
}
}
for(int i = 0; i < n; i++){
for(int j = 0; j < m; j++){
if(grid[i][j] == 0 && reach[i][j] == numberOfOnes){
ret = min(ret, dist[i][j]);
}
}
}
return ret == INT_MAX ? -1 : ret;
}
};输入
[[1,0,2,0,1],[0,0,0,0,0],[0,0,1,0,0]]
输出
7
573 次查看
