假设我们要在空旷的土地上建造一所房屋，该房屋要以最短的距离到达所有建筑物。我们只能向上，向下，向左和向右四个方向移动。我们有一个值为0、1或2的2D网格，其中-
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：=网格的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