資料結構
網路
關係型資料庫管理系統
作業系統
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 次檢視
