【C++BFS】1162. 地图分析
本文涉及知识点
C++BFS算法
LeetCode1162. 地图分析
你现在手里有一份大小为 n x n 的 网格 grid,上面的每个 单元格 都用 0 和 1 标记好了。其中 0 代表海洋,1 代表陆地。
请你找出一个海洋单元格,这个海洋单元格到离它最近的陆地单元格的距离是最大的,并返回该距离。如果网格上只有陆地或者海洋,请返回 -1。
我们这里说的距离是「曼哈顿距离」( Manhattan Distance):(x0, y0) 和 (x1, y1) 这两个单元格之间的距离是 |x0 - x1| + |y0 - y1| 。
示例 1:

输入:grid = [[1,0,1],[0,0,0],[1,0,1]]
输出:2
解释:
海洋单元格 (1, 1) 和所有陆地单元格之间的距离都达到最大,最大距离为 2。
示例 2:

输入:grid = [[1,0,0],[0,0,0],[0,0,0]]
输出:4
解释:
海洋单元格 (2, 2) 和所有陆地单元格之间的距离都达到最大,最大距离为 4。
提示:
n == grid.length
n == grid[i].length
1 <= n <= 100
grid[i][j] 不是 0 就是 1
C++BFS
曼哈顿距离,某条最短路径p1:{c1,c2 ⋯ \cdots ⋯cn-1,cn} ,则c1到cn-1的最短路径p2经过的单格数是n-1。
用反证法来证明:
如果p2的最短路径经过的单格数大于n-1,则p1经过的单格数也大于n。
如果p2的最短路径经过的单格数小于n-1,则用p2替换p1的前n-1个单格,则p2经过的单格数也小于n-1。
BFS的状态表示:leves[0]记录所有陆地单格,leves[i]记录距离陆地i的海洋单格。
BFS的后续状态:通过next枚举cur的四连通临接点,next必须是海洋。
BFS的初始状态:leves[0]记录所有陆地单格。
BFS的返回值:vDis的最大值,如果为0,则改为-1。
BFS的重复处理:利用vDis出重。
代码
核心代码
class Solution {public:int maxDistance(vector<vector<int>>& grid) {m_r = grid.size();m_c = grid[0].size();vector<vector<pair<int,int>>> vNeiBo(m_r * m_c); auto AddNeiBo =[&](int r,int c,int r1,int c1) {if ((r1 < 0) || (r1 >= m_r)) { return; }if ((c1 < 0) || (c1 >= m_c)) { return; }if (0 != grid[r1][c1]) { return; }vNeiBo[Mask(r, c)].emplace_back(r1, c1);};vector<int> vDis(m_r * m_c,-1);queue<pair<int, int>> que;auto Add = [&](int r, int c,int iDis) {if (-1 != vDis[Mask(r, c)]) { return; }vDis[Mask(r, c)] = iDis;que.emplace(r, c);};for (int r = 0; r < m_r; r++) {for (int c = 0; c < m_c; c++) {AddNeiBo(r, c, r + 1, c);AddNeiBo(r, c, r - 1, c);AddNeiBo(r, c, r , c + 1);AddNeiBo(r, c, r , c - 1);if (1 == grid[r][c]) { Add(r, c, 0); }}}while (que.size()) {const auto [r,c] = que.front();que.pop();for (const auto& [r1,c1] : vNeiBo[Mask(r,c)]) {Add(r1, c1, vDis[Mask(r, c)] + 1);}}const int iMax = *std::max_element(vDis.begin(), vDis.end());return (0 == iMax) ? -1 : iMax;}inline int Mask(int r, int c) { return m_c * r + c; }int m_r, m_c;};
单元测试
vector<vector<int>> grid;TEST_METHOD(TestMethod1){grid = { {1} };auto res = Solution().maxDistance(grid);AssertEx(-1, res);}TEST_METHOD(TestMethod2){grid = { {0} };auto res = Solution().maxDistance(grid);AssertEx(-1, res);}TEST_METHOD(TestMethod11){grid = { {1,0,1},{0,0,0},{1,0,1} };auto res = Solution().maxDistance(grid);AssertEx(2, res);}TEST_METHOD(TestMethod12){grid = { {1,0,0},{0,0,0},{0,0,0} };auto res = Solution().maxDistance(grid);AssertEx(4, res);}

扩展阅读
| 我想对大家说的话 |
|---|
| 工作中遇到的问题,可以按类别查阅鄙人的算法文章,请点击《算法与数据汇总》。 |
| 学习算法:按章节学习《喜缺全书算法册》,大量的题目和测试用例,打包下载。重视操作 |
| 有效学习:明确的目标 及时的反馈 拉伸区(难度合适) 专注 |
| 闻缺陷则喜(喜缺)是一个美好的愿望,早发现问题,早修改问题,给老板节约钱。 |
| 子墨子言之:事无终始,无务多业。也就是我们常说的专业的人做专业的事。 |
| 如果程序是一条龙,那算法就是他的是睛 |
| 失败+反思=成功 成功+反思=成功 |
视频课程
先学简单的课程,请移步CSDN学院,听白银讲师(也就是鄙人)的讲解。
https://edu.csdn.net/course/detail/38771
如何你想快速形成战斗了,为老板分忧,请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176
测试环境
操作系统:win7 开发环境: VS2019 C++17
或者 操作系统:win10 开发环境: VS2022 C++17
如无特殊说明,本算法用**C++**实现。

相关文章:
【C++BFS】1162. 地图分析
本文涉及知识点 CBFS算法 LeetCode1162. 地图分析 你现在手里有一份大小为 n x n 的 网格 grid,上面的每个 单元格 都用 0 和 1 标记好了。其中 0 代表海洋,1 代表陆地。 请你找出一个海洋单元格,这个海洋单元格到离它最近的陆地单元格的距…...
实战:安装ElasticSearch 和常用操作命令
概叙 科普文:深入理解ElasticSearch体系结构-CSDN博客 Elasticsearch各版本比较 ElasticSearch 单点安装 1 创建普通用户 #1 创建普通用户名,密码 [roothlink1 lyz]# useradd lyz [roothlink1 lyz]# passwd lyz#2 然后 关闭xshell 重新登录 ip 地址…...
React-Native 宝藏库大揭秘:精选开源项目与实战代码解析
1. 引言 1.1 React-Native 简介 React-Native 是由 Facebook 开发的一个开源框架,它允许开发者使用 JavaScript 和 React 的编程模型来构建跨平台的移动应用。React-Native 的核心理念是“Learn Once, Write Anywhere”,即学习一次 React 的编程模型&am…...
数据结构:二叉树(链式结构)
文章目录 1. 二叉树的链式结构2. 二叉树的创建和实现相关功能2.1 创建二叉树2.2 二叉树的前,中,后序遍历2.2.1 前序遍历2.2.2 中序遍历2.2.3 后序遍历 2.3 二叉树节点个数2.4 二叉树叶子结点个数2.5 二叉树第k层结点个数2.6 二叉树的深度/高度2.7 二叉树…...
召唤生命,阻止轻生——《生命门外》
本书的目的,就是阻止自杀!拉回那些深陷在这样的思维当中正在挣扎犹豫的人,提醒他们珍爱生命,让更多的人,尤其是年轻人从执迷不悟的犹豫徘徊中幡然醒悟,回归正常的生活。 网络上抱孩子跳桥轻生的母亲&#…...
JVM:栈上的数据存储
文章目录 一、Java虚拟机中的基本数据类型 一、Java虚拟机中的基本数据类型 在Java中有8大基本数据类型: 这里的内存占用,指的是堆上或者数组中内存分配的空间大小,栈上的实现更加复杂。 Java中的8大数据类型在虚拟机中的实现:…...
C#实战 - C#实现发送邮件的三种方法
作者:逍遥Sean 简介:一个主修Java的Web网站\游戏服务器后端开发者 主页:https://blog.csdn.net/Ureliable 觉得博主文章不错的话,可以三连支持一下~ 如有疑问和建议,请私信或评论留言! 前言 当使用 C# 编程…...
数模原理精解【5】
文章目录 二元分布满足要求边际分布条件概率例子1例子2 损失函数概率分布期望值例 参考文献 二元分布 满足要求 连续情况下, φ ( x , y ) \varphi (x,y) φ(x,y)为随机变量 X 、 Y X、Y X、Y的联合概率分布(二元分布),如果以下条件满足: …...
C语言篇——使用运算符将16进制数据反转
比如:将一个16进制0xFD,即11111101,反向,输出10111111,即0xBF。 #include <stdio.h>unsigned char reverseBits(unsigned char num) {unsigned char reverse_num 0;int i;for (i 0; i < 8; i) {if ((num &…...
2025年和2024CFA一级SchweserKaplan Notes 全集 (内附分享链接)
CFA一级notes百度网盘下载 2024年和2025年 CFA一级考纲已经正式发布,相比与老考纲,新考纲变化实在不算小。 2024年和2025年 CFA一级notes完整版全 https://drive.uc.cn/s/6394c0b6b1a54?public1 2024年和2025年 cfa二级notes完整版全 https://driv…...
B树的实现:代码示例与解析
B树的实现:代码示例与解析 引言 B树是一种自平衡的树数据结构,广泛应用于文件系统和数据库系统中。它是一种多路搜索树,旨在保持数据有序并允许高效的查找、插入和删除操作。本文将深入探讨B树的实现,提供完整的代码示例和详细的…...
HCIA总结
一、情景再现:ISP网络为学校提供了DNS服务,所以,DNS服务器驻留在ISP网络内,而不再学校网络内。DHCP服务器运行在学校网络的路由器上 小明拿了一台电脑,通过网线,接入到校园网内部。其目的是为了访问谷歌网站…...
软件测试_接口测试面试题
接口测试是软件测试中的重要环节,它主要验证系统不同模块之间的通信和数据交互是否正常。在软件开发过程中,各个模块之间的接口是实现功能的关键要素,因此对接口进行全面而准确的测试是确保系统稳定性和可靠性的关键步骤。 接口测试的核心目…...
C++初阶学习第五弹——类与对象(下)
类与对象(上):C初阶学习第三弹——类与对象(上)-CSDN博客 类和对象(中):C初阶学习第四弹——类与对象(中)-CSDN博客 一.赋值运算符重载 1.1 运算符重载 C为…...
最低工资标准数据(2001-2023年不等)、省市县,整理好的面板数据(excel格式)
时间范围:2001-2022年 具体内容:一:最低工资数据标准时间:2012-2021包含指标: 省份城市/区县小时最低工资标准(非全日制)月最低工资标准实施日期 样例数据: 二:各省最低…...
计算机毕业设计选题推荐-戏曲文化体验系统-Java/Python项目实战
✨作者主页:IT毕设梦工厂✨ 个人简介:曾从事计算机专业培训教学,擅长Java、Python、微信小程序、Golang、安卓Android等项目实战。接项目定制开发、代码讲解、答辩教学、文档编写、降重等。 ☑文末获取源码☑ 精彩专栏推荐⬇⬇⬇ Java项目 Py…...
【深度学习】CosyVoice,论文
CosyVoice_v1.pdf 文章目录 CosyVoice: A Scalable Multilingual Zero-shot Text-to-speech Synthesizer based on Supervised Semantic Tokens摘要1 引言2 CosyVoice: 使用监督语义标记的可扩展TTS模型2.1 用于语音的监督语义标记2.2 用于TTS的大型语言模型2.3 最优传输条件流…...
PHP8.3.9安装记录,Phpmyadmin访问提示缺少mysqli
ubuntu 22.0.4 腾讯云主机 下载好依赖 sudo apt update sudo apt install -y build-essential libxml2-dev libssl-dev libcurl4-openssl-dev pkg-config libbz2-dev libreadline-dev libicu-dev libsqlite3-dev libwebp-dev 下载php8.3.9安装包 nullhttps://www.php.net/d…...
[译] 深入浅出Rust基金会
本篇是对 RustConf 2023中的Rust Foundation: Demystified这一视频的翻译与整理, 过程中为符合中文惯用表达有适当删改, 版权归原作者所有. 大家好,我是Sage Griffin,我的代词是they/them。我今天来这里是要谈谈Rust基金会。 要了解基金会实际做什么,我们需要理解美国国内税收…...
Postman:API开发与测试的强大伴侣
在当今的数字化时代,API(应用程序编程接口)已成为不同软件系统之间通信的桥梁,它们如同数字世界的“翻译官”,使得数据和服务能够在不同的平台和应用程序之间无缝流动。然而,API的开发、测试和维护并非易事…...
python打卡day49
知识点回顾: 通道注意力模块复习空间注意力模块CBAM的定义 作业:尝试对今天的模型检查参数数目,并用tensorboard查看训练过程 import torch import torch.nn as nn# 定义通道注意力 class ChannelAttention(nn.Module):def __init__(self,…...
Golang 面试经典题:map 的 key 可以是什么类型?哪些不可以?
Golang 面试经典题:map 的 key 可以是什么类型?哪些不可以? 在 Golang 的面试中,map 类型的使用是一个常见的考点,其中对 key 类型的合法性 是一道常被提及的基础却很容易被忽视的问题。本文将带你深入理解 Golang 中…...
AtCoder 第409场初级竞赛 A~E题解
A Conflict 【题目链接】 原题链接:A - Conflict 【考点】 枚举 【题目大意】 找到是否有两人都想要的物品。 【解析】 遍历两端字符串,只有在同时为 o 时输出 Yes 并结束程序,否则输出 No。 【难度】 GESP三级 【代码参考】 #i…...
Leetcode 3577. Count the Number of Computer Unlocking Permutations
Leetcode 3577. Count the Number of Computer Unlocking Permutations 1. 解题思路2. 代码实现 题目链接:3577. Count the Number of Computer Unlocking Permutations 1. 解题思路 这一题其实就是一个脑筋急转弯,要想要能够将所有的电脑解锁&#x…...
2025 后端自学UNIAPP【项目实战:旅游项目】6、我的收藏页面
代码框架视图 1、先添加一个获取收藏景点的列表请求 【在文件my_api.js文件中添加】 // 引入公共的请求封装 import http from ./my_http.js// 登录接口(适配服务端返回 Token) export const login async (code, avatar) > {const res await http…...
自然语言处理——Transformer
自然语言处理——Transformer 自注意力机制多头注意力机制Transformer 虽然循环神经网络可以对具有序列特性的数据非常有效,它能挖掘数据中的时序信息以及语义信息,但是它有一个很大的缺陷——很难并行化。 我们可以考虑用CNN来替代RNN,但是…...
Swagger和OpenApi的前世今生
Swagger与OpenAPI的关系演进是API标准化进程中的重要篇章,二者共同塑造了现代RESTful API的开发范式。 本期就扒一扒其技术演进的关键节点与核心逻辑: 🔄 一、起源与初创期:Swagger的诞生(2010-2014) 核心…...
return this;返回的是谁
一个审批系统的示例来演示责任链模式的实现。假设公司需要处理不同金额的采购申请,不同级别的经理有不同的审批权限: // 抽象处理者:审批者 abstract class Approver {protected Approver successor; // 下一个处理者// 设置下一个处理者pub…...
处理vxe-table 表尾数据是单独一个接口,表格tableData数据更新后,需要点击两下,表尾才是正确的
修改bug思路: 分别把 tabledata 和 表尾相关数据 console.log() 发现 更新数据先后顺序不对 settimeout延迟查询表格接口 ——测试可行 升级↑:async await 等接口返回后再开始下一个接口查询 ________________________________________________________…...
论文阅读:Matting by Generation
今天介绍一篇关于 matting 抠图的文章,抠图也算是计算机视觉里面非常经典的一个任务了。从早期的经典算法到如今的深度学习算法,已经有很多的工作和这个任务相关。这两年 diffusion 模型很火,大家又开始用 diffusion 模型做各种 CV 任务了&am…...
