Leetcode #317:离建筑物最近的距离

您所在的位置:网站首页 距离你最近的地方 Leetcode #317:离建筑物最近的距离

Leetcode #317:离建筑物最近的距离

2024-07-17 02:53| 来源: 网络整理| 查看: 265

Leetcode #317:离建筑物最近的距离 题目题干示例 题解PythonC++

题目 题干

该问题离建筑物最近的距离 题面:

You want to build a house on an empty land which reaches all buildings in the shortest amount of distance. You can only move up, down, left and right. You are given a 2D grid of values 0, 1 or 2, where: Each 0 marks an empty land which you can pass by freely. Each 1 marks a building which you cannot pass through. Each 2 marks an obstacle which you cannot pass through.

你是个房地产开发商,想要选择一片空地建一栋大楼。你想把这栋大楼够造在一个距离周边设施都比较方便的地方,通过调研,你希望从它出发能在 最短的距离和 内抵达周边全部的建筑物。请你计算出这个最佳的选址到周边全部建筑物的 最短距离和。

注意: 你只能通过向上、下、左、右四个方向上移动。 给你一个由 0、1 和 2 组成的二维网格,其中: 0 代表你可以自由通过和选择建造的空地 1 代表你无法通行的建筑物 2 代表你无法通行的障碍物

示例

示例 1: 输入: [[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。

题解

主要思路: (1)使用广度优先搜索,从每个建筑出发,找能到达的各个空地的距离,从所有建筑都能到达的空地中选择一个距离最小的值; (2)使用两个数组进行辅助,一个用来辅助记录从建筑出发的到各个空地的距离,一个用来辅助记录各个建筑到某个空地的距离和,最后从其中选择一个所有的建筑都能到达的空地的最小值作为结果;

Python import sys INT_MAX = sys.maxsize class Solution: def __init__(self, grids): self.grids = grids def short_dis(self): rows = len(self.grids) cols = len(self.grids[0]) # 记录各建筑到各空格距离 dist = [[0] * cols for i in range(rows)] # 记录各建筑到各空格距离之和 sum_dist = [[0] * cols for i in range(rows)] # 可以移动的方向 step = [(0, 1), (0, -1), (1, 0), (-1, 0)] # 标识之前的各建筑都能到达的空格,减少计算量 times = 0 res = INT_MAX for i in range(rows): for j in range(cols): if self.grids[i][j] == 1: # 若当前位置是建筑,从该位置开始进行广度优先搜索 res = INT_MAX q = [(i, j)] # 广度优先搜索存储结构 while len(q) > 0: cur_pos = q.pop(0) # 辅助变量,当前点 for k in range(len(step)): # 尝试的四个方向 # 当前位置 x = cur_pos[0] + step[k][0] y = cur_pos[1] + step[k][1] # 若当前位置没有越界,既有效,且之前的各个建筑都能够到达 if 0


【本文地址】


今日新闻


推荐新闻


CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3