​LeetCode刷题实战317:离建筑物最近的距离

算法的重要性,我就不多说了吧,想去大厂,就必须要经过基础知识和业务逻辑面试+算法面试。所以,为了提高大家的算法能力,这个公众号后续每天带大家做一道算法题,题目就从LeetCode上面选 !

今天和大家聊的问题叫做 离建筑物最近的距离,我们先来看题面:
https://leetcode-cn.com/problems/shortest-distance-from-all-buildings/

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 代表你无非通行的障碍物


示例

​LeetCode刷题实战317:离建筑物最近的距离

解题


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

class Solution {
public:
    int shortestDistance(vector<vector<int>>& grid) {
        int rows=grid.size();
        int cols=grid[0].size();
        //记录各个建筑到各个空格的距离
        vector<vector<int>> dist(rows,vector<int>(cols,0));
        //记录各个建筑能到各个空格的距离之和
        vector<vector<int>> sum_dist(rows,vector<int>(cols,0));
        //可以移动的方向
        vector<vector<int>> step={{0,1},{0,-1},{1,0},{-1,0}};
        //主要标识之前的各个建筑都能到达的空格,这样减少计算量
        int times=0;
        int res=INT_MAX;//从当前各个建筑都能到达的空地中,找出最小的距离之和值
        //遍历各个位置
        for(int i=0;i<rows;++i){
            for(int j=0;j<cols;++j){
                if(grid[i][j]==1){//若当前位置是建筑,从该位置开始进行广度优先搜索
                    res=INT_MAX;//初始化该值
                    pair<int,int> cur_pos;//辅助变量
                    queue<pair<int,int>> q;//广度优先搜索存储结构
                    q.push({i,j});//初始化
                    while(!q.empty()){
                        cur_pos=q.front();//当前点
                        q.pop();
                        for(int k=0;k<step.size();++k){//尝试的四个方向
                          //尝试的位置
                            int x=cur_pos.first+step[k][0];
                            int y=cur_pos.second+step[k][1];
                            //若当前位置没有越界,既有效,且之前的各个建筑都能够到达
                            if(x>=0&&x<rows&&y>=0&&y<cols&&grid[x][y]==times){
                              //则更新当前距离
                                dist[x][y]=dist[cur_pos.first][cur_pos.second]+1;
                                //更新对应的距离之和
                                sum_dist[x][y]+=dist[x][y];
                                //保存最小的距离和
                                res=min(res,sum_dist[x][y]);
                                //对应的值减一,标识当前建筑也访问过
                                --grid[x][y];
                                //压入当前位置
                                q.push({x,y});
                            }
                        }
                    }
                    //若该值没有变化,说明该建筑不能到达之前建筑都到达过的空地,则直接返回-1
                    if(res==INT_MAX){
                        return -1;
                    }
                    //标识当前建筑也访问过
                    --times;
                }
            }
        }
        return res;
    }
};

好了,今天的文章就到这里,如果觉得有所收获,请顺手点个在看或者转发吧,你们的支持是我最大的动力 。

上期推文:

LeetCode1-300题汇总,希望对你有点帮助!
LeetCode刷题实战301:删除无效的括号
LeetCode刷题实战302:包含全部黑色像素的最小矩阵
LeetCode刷题实战303:区域和检索 – 数组不可变
LeetCode刷题实战304:二维区域和检索 – 矩阵不可变
LeetCode刷题实战305:岛屿数量II
LeetCode刷题实战306:累加数
LeetCode刷题实战307:区域和检索 – 数组可修改
LeetCode刷题实战308:二维区域和检索 – 可变
LeetCode刷题实战309:最佳买卖股票时机含冷冻期
LeetCode刷题实战310:最小高度树
LeetCode刷题实战311:稀疏矩阵的乘法
LeetCode刷题实战312:戳气球
LeetCode刷题实战313:超级丑数
LeetCode刷题实战314:二叉树的竖直遍历
LeetCode刷题实战315:计算右侧小于当前元素的个数
LeetCode刷题实战316:去除重复字母

​LeetCode刷题实战317:离建筑物最近的距离

原创文章,作者:栈长,如若转载,请注明出处:https://www.cxyquan.com/12594.html

发表评论

登录后才能评论

联系我们

400-800-8888

在线咨询:点击这里给我发消息

邮件:admin@example.com

工作时间:周一至周五,9:30-18:30,节假日休息