崂山区城市规划建设局网站,wordpress update_option,wordpress 账号图片,WordPress如何获取logo文章目录1. 题目2. 解题2.1 正常思维BFS2.2 逆向思考BFS1. 题目
你是个房地产开发商#xff0c;想要选择一片空地 建一栋大楼。 你想把这栋大楼够造在一个距离周边设施都比较方便的地方#xff0c;通过调研#xff0c;你希望从它出发能在 最短的距离和 内抵达周边全部的建筑…
文章目录1. 题目2. 解题2.1 正常思维BFS2.2 逆向思考BFS1. 题目
你是个房地产开发商想要选择一片空地 建一栋大楼。 你想把这栋大楼够造在一个距离周边设施都比较方便的地方通过调研你希望从它出发能在 最短的距离和 内抵达周边全部的建筑物。 请你计算出这个最佳的选址到周边全部建筑物的 最短距离和。
提示 你只能通过向上、下、左、右四个方向上移动。
给你一个由 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) 的障碍物。
由于总距离之和 3317 最优所以位置 (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(vectorvectorint grid) {vectorvectorint dir {{1,0},{0,1},{0,-1},{-1,0}};vectorvectorint 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;queuevectorint q;vectorvectorbool visited(m, vectorbool(n,false));q.push({pos[0], pos[1]});//x,yvisited[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(i0 im j0 jn !visited[i][j] grid[i][j]!2){visited[i][j] true;if(grid[i][j]1)//找到一个房子{count;dis d;}else// (grid[i][j]0)q.push({i,j});}}}}if(count building_nums){ //找到了所有房子mindis min(mindis, dis);}}return mindisINT_MAX ? -1 : mindis;}
};2.2 逆向思考BFS
从每个房屋出发dis 数组记录每个房屋到空地的距离totaldis 数组记录每个房子遍历空地后之前所有房子到空地的总距离
class Solution {
public:int shortestDistance(vectorvectorint grid) {//从每个建筑物出发去找空地空地对每个建筑物的距离累积vectorvectorint dir {{1,0},{0,1},{0,-1},{-1,0}};vectorvectorint 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});vectorvectorint dis(m, vectorint(n, 0));//记录单次遍历1个房屋到空地的距离vectorvectorint totaldis(m, vectorint(n, 0));//记录所有房屋到空地的距离int emptyPlace 0;//空地的标记数字for(auto pos : build)//遍历房子{queuevectorint q;// vectorvectorbool visited(m, vectorbool(n,false));q.push({pos[0], pos[1]});//x,ymindis 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(i0 im j0 jn grid[i][j] emptyPlace)//空地{dis[i][j] dis[x][y]1;//该房子到ij空地的距离totaldis[i][j] dis[i][j];//之前所有房子到这的距离和mindis min(mindis, totaldis[i][j]);// visited[i][j] true;grid[i][j]--;//从lx_lx大佬那学的不用开访问数组了q.push({i,j});}}}if(mindis INT_MAX)return -1;//该房屋不能到达任何空地emptyPlace--;//更新空地的标记免开访问标记数组}return mindisINT_MAX ? -1 : mindis;}
};36 ms 11.9 MB 我的CSDN博客地址 https://michael.blog.csdn.net/
长按或扫码关注我的公众号Michael阿明一起加油、一起学习进步
