当前位置: 首页 > ds >正文

LeetCode 317 离建筑物最近的距离

LeetCode 317 题的详细题目信息如下:

题目名称

Shortest Distance from All Buildings(中文译名:离建筑物最近的距离)

题目描述

给你一个由 0、1 和 2 组成的二维网格,其中:

  • 0 代表空地
  • 1 代表建筑物
  • 2 代表障碍物

你需要找到一个空地,使其到所有建筑物的总曼哈顿距离之和最小。如果不存在这样的空地(即没有任何空地能到达所有建筑物),则返回 -1。

曼哈顿距离的计算方式为:对于两个点 (x1, y1) 和 (x2, y2),其距离为 |x1 - x2| + |y1 - y2|。

示例

输入

[[1,0,2,0,1],[0,0,0,0,0],[0,0,1,0,0]
]

输出:7
解释
网格中共有 3 个建筑物。位于 (1,2) 的空地到所有建筑物的总距离为 7(到 (0,0) 的距离为 3,到 (0,4) 的距离为 3,到 (2,2) 的距离为 1,总和 3+3+1=7),是所有符合条件的空地中最小的。

约束条件

  • 网格的行数和列数均不超过 100。
  • 网格中至少有一个建筑物。

LeetCode 317. 离建筑物最近的距离 详细解题代码

/*** @param {number[][]} grid* @return {number}*/
var shortestDistance = function(grid) {// 边界条件判断:网格为空或行数/列数为0if (!grid || grid.length === 0 || grid[0].length === 0) {return -1;}const rows = grid.length;const cols = grid[0].length;let buildingCount = 0; // 记录建筑物的总数量// 存储每个空地到所有建筑物的距离之和const distanceSum = Array.from({ length: rows }, () => Array(cols).fill(0));// 存储每个空地能到达的建筑物数量const reachCount = Array.from({ length: rows }, () => Array(cols).fill(0));// 遍历网格中的每个单元格for (let i = 0; i < rows; i++) {for (let j = 0; j < cols; j++) {// 当遇到建筑物时,执行BFS计算距离if (grid[i][j] === 1) {buildingCount++;const queue = [[i, j, 0]]; // BFS队列,元素为[行, 列, 距离]const visited = Array.from({ length: rows }, () => Array(cols).fill(false));visited[i][j] = true; // 标记建筑物自身为已访问// BFS循环while (queue.length > 0) {const [curRow, curCol, dist] = queue.shift(); // 取出队首元素// 遍历四个方向(上、下、左、右)const directions = [[-1, 0], [1, 0], [0, -1], [0, 1]];for (const [dr, dc] of directions) {const newRow = curRow + dr;const newCol = curCol + dc;// 检查新坐标是否有效:在网格范围内、未访问过、且是空地if (newRow >= 0 && newRow < rows && newCol >= 0 && newCol < cols && !visited[newRow][newCol] && grid[newRow][newCol] === 0) {visited[newRow][newCol] = true; // 标记为已访问distanceSum[newRow][newCol] += dist + 1; // 累加距离reachCount[newRow][newCol]++; // 增加可到达的建筑物数量queue.push([newRow, newCol, dist + 1]); // 加入队列继续BFS}}}}}}// 寻找最小的距离和let minDistance = Infinity;for (let i = 0; i < rows; i++) {for (let j = 0; j < cols; j++) {// 只有空地且能到达所有建筑物时,才参与最小距离计算if (grid[i][j] === 0 && reachCount[i][j] === buildingCount) {minDistance = Math.min(minDistance, distanceSum[i][j]);}}}// 如果没有符合条件的空地,返回-1,否则返回最小距离return minDistance === Infinity ? -1 : minDistance;
};// 测试用例
const grid = [[1, 0, 2, 0, 1],[0, 0, 0, 0, 0],[0, 0, 1, 0, 0]
];
console.log(shortestDistance(grid)); // 输出:7

代码思路解析

  1. 初始化:创建两个二维数组 distanceSum 和 reachCount,分别用于记录每个空地到所有建筑物的距离总和以及能到达的建筑物数量。
  2. BFS 遍历:对每个建筑物执行 BFS,计算其到所有可达空地的距离,并更新 distanceSum 和 reachCount
  3. 筛选最优解:遍历所有空地,找到能到达所有建筑物(reachCount[i][j] 等于建筑物总数)且距离总和最小的空地。
  4. 边界处理:若不存在符合条件的空地,返回 -1,否则返回最小距离。

该解法通过 BFS 保证了距离计算的准确性,时间复杂度为 O (B×N×M)(其中 B 为建筑物数量,N 和 M 为网格的行数和列数),适用于题目给定的约束条件。

http://www.xdnf.cn/news/19244.html

相关文章:

  • 科技赋能医疗:陪诊小程序系统开发,让就医不再孤单
  • mysql中表的约束
  • weblogic JBoss漏洞 Strcts2漏洞 fastjson漏洞
  • 计算机视觉第一课opencv(四)保姆级教学
  • solidity地址、智能合约、交易概念
  • 【完整源码+数据集+部署教程】高速公路施工区域物体检测系统源码和数据集:改进yolo11-RepNCSPELAN
  • FOC-双电阻采样-无刷-AC/DC(吹风筒项目)
  • 笔记本电脑频繁出现 vcomp140.dll丢失怎么办?结合移动设备特性,提供适配性强的修复方案
  • 函数的逆与原象
  • flutter-使用url_launcher打开链接/应用/短信/邮件和评分跳转等
  • LoraConfig target modules加入embed_tokens(64)
  • Java项目打包成EXE全攻略
  • Spring Boot 项目文件上传安全与优化:OSS、MinIO、Nginx 分片上传实战
  • 用 C++ 创建单向链表 forward list
  • “我店 + RWA”来袭:重构商业价值,解锁消费投资新密码
  • HarmonyOS权限管理应用
  • 【序列晋升】20 Spring Cloud Function 函数即服务(FaaS)
  • FPGA实现1553B BC控制器IP方案
  • LeetCode259~282题解
  • 吴恩达机器学习作业五:神经网络正向传播
  • 【前端教程】从性别统计类推年龄功能——表单交互与数据处理进阶
  • 【前端教程】从零开始学JavaScript交互:7个经典事件处理案例解析
  • C++Primer笔记——第六章:函数(下)
  • KNN算法(K近邻算法)
  • 互联网大厂AI大模型面试解析:从基础技术到场景应用
  • STL容器的连续性及其访问:vector和deque
  • 零基础上手:Cursor + MCP 爬取 YouTube 视频数据
  • 微信小程序中蓝牙打印机中文编码处理:使用iconv-lite库
  • Pytest 插件:pytest_runtest_protocol
  • 在Excel和WPS表格中隔一行插入多个空白行