生活随笔
收集整理的這篇文章主要介紹了
LeetCode 317. 离建筑物最近的距离（逆向BFS）*
小編覺得挺不錯的,現在分享給大家,幫大家做個參考.
文章目錄
1. 題目
你是個房地產開發商，想要選擇一片空地 建一棟大樓。
你想把這棟大樓夠造在一個距離周邊設施都比較方便的地方，通過調研，你希望從它出發能在 最短的距離和 內抵達周邊全部的建筑物。
請你計算出這個最佳的選址到周邊全部建筑物的 最短距離和。
提示：
你只能通過向上、下、左、右四個方向上移動。
給你一個由 0、1 和 2 組成的二維網格，其中：
- 0 代表你可以自由通過和選擇建造的空地
- 1 代表你無法通行的建筑物
- 2 代表你無法通行的障礙物
示例：
輸入：
[[1,0,2,0,1],[0,0,0,0,0],[0,0,1,0,0]]
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。注意：
題目數據保證至少存在一棟建筑物，如果無法按照上述規則返回建房地點，則請你返回
-1。
來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/shortest-distance-from-all-buildings
著作權歸領扣網絡所有。商業轉載請聯系官方授權，非商業轉載請注明出處。
2. 解題
2.1 正常思維BFS
59 / 72 個通過測試用例
- 從每個空地出發，其找所有的房屋，空地如果非常多，復雜度為O(m2n2)
class Solution {
public:int shortestDistance(vector
<vector
<int>>& grid
) {vector
<vector
<int>> dir
= {{1,0},{0,1},{0,-1},{-1,0}};vector
<vector
<int>> place
;int i
, j
, k
, x
, y
, building_nums
= 0, count
, mindis
= INT_MAX
, dis
, d
, size
;int m
= grid
.size(), n
= grid
[0].size();for(i
= 0; i
< m
; i
++)for(j
= 0; j
< n
; j
++)if(grid
[i
][j
]==0)place
.push_back({i
,j
});else if(grid
[i
][j
]==1)building_nums
++;for(auto& pos
: place
){count
= 0;dis
= 0;d
= 0;queue
<vector
<int>> q
;vector
<vector
<bool>> visited(m
, vector
<bool>(n
,false));q
.push({pos
[0], pos
[1]});visited
[pos
[0]][pos
[1]] = true;while(!q
.empty()){size
= q
.size();d
++;if(dis
>= mindis
)break;while(size
--){x
= q
.front()[0];y
= q
.front()[1];q
.pop();for(k
= 0; k
< 4; ++k
){i
= x
+ dir
[k
][0];j
= y
+ dir
[k
][1];if(i
>=0 && i
<m
&& j
>=0 && j
<n
&& !visited
[i
][j
] && grid
[i
][j
]!=2){visited
[i
][j
] = true;if(grid
[i
][j
]==1){count
++;dis
+= d
;}elseq
.push({i
,j
});}}}}if(count
== building_nums
){ mindis
= min(mindis
, dis
);}}return mindis
==INT_MAX
? -1 : mindis
;}
};
2.2 逆向思考BFS
- 從每個房屋出發，dis 數組記錄每個房屋到空地的距離
- totaldis 數組記錄，每個房子遍歷空地后，之前所有房子到空地的總距離
class Solution {
public:int shortestDistance(vector
<vector
<int>>& grid
) {vector
<vector
<int>> dir
= {{1,0},{0,1},{0,-1},{-1,0}};vector
<vector
<int>> build
;int i
, j
, k
, x
, y
, mindis
;int m
= grid
.size(), n
= grid
[0].size();for(i
= 0; i
< m
; i
++)for(j
= 0; j
< n
; j
++)if(grid
[i
][j
]==1)build
.push_back({i
,j
});vector
<vector
<int>> dis(m
, vector
<int>(n
, 0));vector
<vector
<int>> totaldis(m
, vector
<int>(n
, 0));int emptyPlace
= 0;for(auto& pos
: build
){queue
<vector
<int>> q
;q
.push({pos
[0], pos
[1]});mindis
= INT_MAX
;while(!q
.empty()){x
= q
.front()[0];y
= q
.front()[1];q
.pop();for(k
= 0; k
< 4; ++k
){i
= x
+ dir
[k
][0];j
= y
+ dir
[k
][1];if(i
>=0 && i
<m
&& j
>=0 && j
<n
&& grid
[i
][j
] == emptyPlace
){dis
[i
][j
] = dis
[x
][y
]+1;totaldis
[i
][j
] += dis
[i
][j
];mindis
= min(mindis
, totaldis
[i
][j
]);grid
[i
][j
]--;q
.push({i
,j
});}}}if(mindis
== INT_MAX
)return -1;emptyPlace
--;}return mindis
==INT_MAX
? -1 : mindis
;}
};
36 ms 11.9 MB
我的CSDN博客地址 https://michael.blog.csdn.net/
長按或掃碼關注我的公眾號（Michael阿明），一起加油、一起學習進步！
總結
以上是生活随笔為你收集整理的LeetCode 317. 离建筑物最近的距离（逆向BFS）*的全部內容，希望文章能夠幫你解決所遇到的問題。
如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。
