与C ++中所有建筑物的最短距离
假设我们要在空旷的土地上建造一所房屋，该房屋要以最短的距离到达所有建筑物。我们只能向上，向下，向左和向右四个方向移动。我们有一个值为0、1或2的2D网格，其中-
0代表我们可以自由经过的空地。
1代表我们无法通过的建筑物。
2代表我们无法通过的障碍。
所以，如果输入像
则输出将为7，因为给定三栋建筑物位于(0,0)，(0,4)，(2,2)，并且障碍物位于(0,2)，因此点(1,2)为理想的空地来盖房，因为总行驶距离为3+3+1=7最小。
为了解决这个问题，我们将遵循以下步骤-
ret：=inf
n：=网格的行大小
m：=网格的col大小
numberOfOnes：=0
定义大小为nxm的2D数组dist
定义一个尺寸为nxm的2D阵列范围
对于初始化i：=0，当i<n时，更新（将i增加1），执行-
如果grid[i，j]与1相同，则-
sz：=q的大小
当sz为非零值时，请在每次迭代中减少sz，请执行-
nx：=x+dir[k，0]
ny：=y+dir[k，1]
如果nx和ny在grid的范围内，或者grid[nx，ny]不为0，则
忽略以下部分，跳至下一个迭代
将{nx，ny}插入访问
dist[nx，ny]：=dist[nx，ny]+lvl
（将覆盖率[nx，ny]增加1）
将{nx，ny}插入q
curr：=q的第一个元素
从q删除元素
x：=curr.first
y：=curr.second
对于初始化k：=0，当k<4时，更新（将k增加1），执行-
（将numberOfOnes增加1）
定义一个队列q
将{i，j}插入q
定义一组参观
对于初始化lvl：=1，当非q为空时，更新（将lvl增加1），执行-
对于初始化j：=0，当j<m时，更新（将j增加1），执行-
对于初始化i：=0，当i<n时，更新（将i增加1），执行-
如果grid[i，j]与0相同，而reach[i，j]与numberOfOnes相同，则-
ret：=ret和dist[i，j]的最小值
对于初始化j：=0，当j<m时，更新（将j增加1），执行-
返回（如果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