生活随笔
收集整理的这篇文章主要介绍了
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）*的全部内容，希望文章能够帮你解决所遇到的问题。
如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。
