《剑指 Offer》专项突破版 - 面试题 107 : 矩阵中的距离(C++ 实现)
题目链接:矩阵中的距离
题目:
输入一个由 0、1 组成的矩阵 M,请输出一个大小相同的矩阵 D,矩阵 D 中的每个格子是矩阵 M 中对应格子离最近的 0 的距离。水平或竖直方向相邻的两个格子的距离为 1。假设矩阵 M 中至少有一个 0。
例如,下图 (a) 是一个只包含 0、1 的矩阵 M,它的每个格子离最近的 0 的距离如下图 (b) 的矩阵 D 所示。M[0][0] 等于 0,因此它离最近的 0 的距离是 0,所以 D[0][0] 等于 0。M[2][1] 等于 1,离它最近的 0 的坐标是 (0, 1)、(1, 0)、(1, 2),它们离坐标 (2, 1) 的距离都是 2,所以 D[2][1] 等于 2。
分析:
应用与图相关的算法解决问题的前提是能够找出图中的节点和边。这是一个背景为矩阵的问题,矩阵中的每个格子可以看成图中的一个节点,矩阵中上、下、左、右相邻的格子对应的节点之间有一条边相连。例如,可以将上图 (a) 中的矩阵看成下图所示的图。
这个题目要求计算每个格子离最近的 0 的距离。根据题目的要求,上、下、左、右相邻的两个格子的距离为 1。可以将图看成一个无权图,图中两个节点的距离是连通它们的路径经过的边的数目。由于这个问题与无权图的最近距离相关,因此可以考虑应用广度优先搜索解决。
广度优先搜索需要一个队列。图中的哪些节点可以当作初始节点添加到队列中?这个问题是求每个格子离最近的 0 的距离,因此可以将所有的 0 当作初始节点添加到队列中,然后以值为 0 的节点作为起点做广度优先搜索。当经过 d 步到达某个格子,那么该格子离最近的 0 的距离就是 d。
class Solution {
public:vector<vector<int>> updateMatrix(vector<vector<int>>& mat) {int rows = mat.size(), cols = mat[0].size();vector<vector<int>> dists(rows, vector<int>(cols));
queue<vector<int>> q;for (int i = 0; i < rows; ++i){for (int j = 0; j < cols; ++j){if (mat[i][j] == 0){dists[i][j] = 0;q.push(vector<int>{ i, j });}else{dists[i][j] = INT_MAX;}}}
vector<vector<int>> dirs = { { -1, 0 }, { 1, 0 }, { 0, -1 }, { 0, 1 } };while (!q.empty()){vector<int> coord = q.front();q.pop();int dist = dists[coord[0]][coord[1]];
for (vector<int>& dir : dirs){int r = coord[0] + dir[0];int c = coord[1] + dir[1];if (r >= 0 && r < rows && c >= 0 && c < cols){if (dists[r][c] > dist + 1){dists[r][c] = dist + 1;q.push(vector<int>{ r, c });}}}}return dists;}
};
上述代码创建了一个大小与输入矩阵 mat 相同的二维数组 dists,用来记录每个格子离最近的 0 的距离。如果 mat[i][j] 为 0,那么这个格子离最近的 0 的距离自然是 0,因此 dists[i][j] 设为 0。如果 mat[i][j] 的值为 1,则先用最大的整数值初始化 dists[i][j],接下来搜索到对应的节点时再更新它的值。
队列中的元素是矩阵中格子的坐标,是一个长度为 2 的数组。一个格子的坐标被添加到队列中之前,它离最近的 0 的距离已经计算好并且保存在数组 dists 中。
每次从队列中取出一个坐标为 coord 的格子,该格子离最近的 0 的距离用变量 dist 表示。从该格子出发沿着上、下、左、右到达坐标为 (r, c) 的格子。如果该格子之前没有到达过,此时 dists[r][c] 的值仍然为最大的整数值,那么 dists[r][c] > dist + 1 的值为 true。由于是从离最近的 0 的距离为 dist 的格子多走一步到达该格子的,因此该格子离最近的 0 的距离是 dist + 1。此外,还需要将该格子添加到队列中,以便接下来搜索与该格子相连的其他节点。
如果之前已经到达坐标为 (r, c) 的格子,那么 dist[r][c] 的值一定不可能大于 dist + 1。这是因为用的是广度优先搜索,而广度优先搜索能够保证从起始节点到达任意节点一定是沿着最短路径的。当第 1 次到达坐标为 (r, c) 的格子时记录到 dists[r][c] 的值一定是从值为 0 的格子到达该格子的最短距离。因此,当再次到达坐标为 (r, c) 的格子时,dists[r][c] > dist + 1 的值为 false。通过比较距离可以避免重复访问某个格子。
相关文章:

《剑指 Offer》专项突破版 - 面试题 107 : 矩阵中的距离(C++ 实现)
题目链接:矩阵中的距离 题目: 输入一个由 0、1 组成的矩阵 M,请输出一个大小相同的矩阵 D,矩阵 D 中的每个格子是矩阵 M 中对应格子离最近的 0 的距离。水平或竖直方向相邻的两个格子的距离为 1。假设矩阵 M 中至少有一个 0。 …...

揭秘智慧礼品背后的故事
如若不是从事技术行业,在罗列礼品清单时,可能不会想到 “数据”,但幸运的是,我们想到了。如何将AI技术应用到当季一些最受青睐的产品中去,训练数据是这一智能技术的背后动力。很多电子设备或名称中带有“智能”一词的设…...

NVM的安装与配置
目录 一、简介二、下载2.1、windows环境下载地址2.2、安装 三、配置3.1、查看可安装版本3.2、安装版本3.3、使用和切换版本3.4、模块配置 四、其他4.1、全局安装pnpm4.2、常用nvm命令 一、简介 NVM,全称为Node Version Manager,是一个流行的命令行工具&a…...

[Java EE] 多线程(一) :线程的创建与常用方法(上)
1. 认识线程 1.1 概念 1.1.1 什么是线程 ⼀个线程就是⼀个"执⾏流".每个线程之间都可以按照顺序执⾏⾃⼰的代码.多个线程之间"同时"执⾏ 着多份代码. 还是回到我们之前的银⾏的例⼦中。之前我们主要描述的是个⼈业务,即⼀个⼈完全处理⾃⼰的…...

Linux安装docker(含Centos系统和Ubuntu系统)
一、Centos系统 1. 卸载旧版本依赖 sudo yum remove docker \docker-client \docker-client-latest \docker-common \docker-latest \docker-latest-logrotate \docker-logrotate \docker-engine 2. 设置仓库 安装所需的软件包。yum-utils 提供了 yum-config-manager &…...

【第十五届蓝桥杯大赛软件赛省赛】———— C/C++ 大学B组
蓝桥杯2024年15届省赛b组原题献上...
Redis+lua脚本限制ip多次输入错误密码
Redislua脚本限制ip多次输入错误密码 不能锁username,因为如果有人恶意保留破解密码的话。会导致用户本人无法登录。 这里我采用 以ip的方式进行锁定。利用redis 设置key:ip。value:当前ip尝试登录的次数 实现逻辑 逻辑简单,假设…...

全球顶级的低代码开发平台,你知道几个?
什么是低代码开发平台? 低码开发平台是一个应用程序,提供图形用户界面编程,从而以非常快的速度开发代码,减少了传统的编程工作。 这些工具有助于快速开发代码,最大限度地减少手工编码的努力。这些平台不仅有助于编码,而且还能快速安装和部署。 低码开发工具的好处 低代码平…...
11-1.Vue2.x基本列表—v-for
文章目录 Vue2.x基本列表—v-for Vue2.x基本列表—v-for <!DOCTYPE html> <html lang"en"><head><meta charset"UTF-8" /><title>基本列表</title><script type"text/javascript" src"../js/vue.j…...

一本书精通推荐算法,轻松搞定入门、面试、进阶
当前互联网高速发展,用户规模和内容规模均迅猛提升。 身处信息严重过载的时代,如何让用户从海量信息中发现自己感兴趣的内容,成了很多公司的核心问题。 在此背景下,搜索系统和推荐系统应运而生。 前者主要解决用户主动寻找内容…...

ADB的基本语法及常用命令
学习网址 ADB命令的基本语法如下: adb [-d|-e|-s <serialNumber>] <command> 如果有多个设备/模拟器连接,则需要为命令指定目标设备。 参数及含义如下: 常用命令如下: 1. 启动ADB服务 adb start-server 2. 停止…...

Linux之bpfjit(2)使用分析和mini-tcpdump实现
Linux之bpfjit(2)使用分析和mini-tcpdump实现 Author: Once Day Date: 2024年4月13日 一位热衷于Linux学习和开发的菜鸟,试图谱写一场冒险之旅,也许终点只是一场白日梦… 漫漫长路,有人对你微笑过嘛… 全系列文章可以参考专栏:…...
adb常用命令汇总
Android Debug Bridge (adb) 是一个多功能命令行工具,它允许你与连接的Android设备或在电脑上的Android模拟器进行通信。下面列出了一些常用的adb命令: 启动adb服务: adb start-server停止adb服务: adb kill-server查看已连接的设…...

JVM虚拟机(三)垃圾回收简介、垃圾回收算法、分代回收、垃圾回收器种类、G1垃圾回收器
目录 一、什么是垃圾回收?1.1 什么是垃圾回收?1.2 什么对象能被垃圾回收?1)引用计数法2)可达性分析算法 二、JVM 垃圾回收算法2.1 标记清除算法2.2 标记整理算法(标记压缩算法)2.3 复制算法2.4 …...

JavaScript基础:js介绍、变量、数据类型以及类型转换
目录 介绍 引入方式 内部方式 外部形式 注释和结束符 单行注释 多行注释 结束符 输入和输出 输出 输入 变量 声明 赋值 关键字 变量名命名规则 常量 数据类型 数值类型 字符串类型 布尔类型 undefined 类型转换 隐式转换 显式转换 Number ✨介绍 &a…...

【牛客SQL快速入门】SQL基础(三)
一、条件函数 IF 条件函数 IF函数是最常用到的条件函数,写法为 if(xn,a,b),xn代表判断条件,如果xn时,那么结果返回a,否则返回b。 -- 把非北京大学的用户统一归为其他大学 Select device_id,if(university ‘北京大…...

Pytorch手撸Attention
Pytorch手撸Attention 注释写的很详细了,对照着公式比较下更好理解,可以参考一下知乎的文章 注意力机制 import torch import torch.nn as nn import torch.nn.functional as Fclass SelfAttention(nn.Module):def __init__(self, embed_size):super(S…...

PyCharm 2024.1 发布:全面升级,助力高效编程!
PyCharm 2024.1 发布:全面升级,助力高效编程! 文章目录 PyCharm 2024.1 发布:全面升级,助力高效编程!摘要引言 Hugging Face:模型和数据集的快速文档预览针对 JavaScript 和 TypeScript 的全行代…...
Nginx基础(06)
Nginx基础(05) uWSGI 介绍 uWSGI 是一个 Web服务器 主要用途是将Web应用程序部署到生产环境中 可以用来连接Nginx服务与Python动态网站 1. 用 uWSGI 部署 Python 网站项目 配置 Nginx 使其可以将动态访问转交给 uWSGI 安装 python 工具及依赖 安…...

【Qt 学习笔记】QWidget的windowOpacity属性 | cursor属性 | font属性
博客主页:Duck Bro 博客主页系列专栏:Qt 专栏关注博主,后期持续更新系列文章如果有错误感谢请大家批评指出,及时修改感谢大家点赞👍收藏⭐评论✍ QWidget的windowOpacity属性 | cursor属性 | font属性 文章编号&#…...

IoT/HCIP实验-3/LiteOS操作系统内核实验(任务、内存、信号量、CMSIS..)
文章目录 概述HelloWorld 工程C/C配置编译器主配置Makefile脚本烧录器主配置运行结果程序调用栈 任务管理实验实验结果osal 系统适配层osal_task_create 其他实验实验源码内存管理实验互斥锁实验信号量实验 CMISIS接口实验还是得JlINKCMSIS 简介LiteOS->CMSIS任务间消息交互…...

Mac下Android Studio扫描根目录卡死问题记录
环境信息 操作系统: macOS 15.5 (Apple M2芯片)Android Studio版本: Meerkat Feature Drop | 2024.3.2 Patch 1 (Build #AI-243.26053.27.2432.13536105, 2025年5月22日构建) 问题现象 在项目开发过程中,提示一个依赖外部头文件的cpp源文件需要同步,点…...
laravel8+vue3.0+element-plus搭建方法
创建 laravel8 项目 composer create-project --prefer-dist laravel/laravel laravel8 8.* 安装 laravel/ui composer require laravel/ui 修改 package.json 文件 "devDependencies": {"vue/compiler-sfc": "^3.0.7","axios": …...
基于Java Swing的电子通讯录设计与实现:附系统托盘功能代码详解
JAVASQL电子通讯录带系统托盘 一、系统概述 本电子通讯录系统采用Java Swing开发桌面应用,结合SQLite数据库实现联系人管理功能,并集成系统托盘功能提升用户体验。系统支持联系人的增删改查、分组管理、搜索过滤等功能,同时可以最小化到系统…...
React从基础入门到高级实战:React 实战项目 - 项目五:微前端与模块化架构
React 实战项目:微前端与模块化架构 欢迎来到 React 开发教程专栏 的第 30 篇!在前 29 篇文章中,我们从 React 的基础概念逐步深入到高级技巧,涵盖了组件设计、状态管理、路由配置、性能优化和企业级应用等核心内容。这一次&…...

基于开源AI智能名片链动2 + 1模式S2B2C商城小程序的沉浸式体验营销研究
摘要:在消费市场竞争日益激烈的当下,传统体验营销方式存在诸多局限。本文聚焦开源AI智能名片链动2 1模式S2B2C商城小程序,探讨其在沉浸式体验营销中的应用。通过对比传统品鉴、工厂参观等初级体验方式,分析沉浸式体验的优势与价值…...
数据库——redis
一、Redis 介绍 1. 概述 Redis(Remote Dictionary Server)是一个开源的、高性能的内存键值数据库系统,具有以下核心特点: 内存存储架构:数据主要存储在内存中,提供微秒级的读写响应 多数据结构支持&…...
FTXUI::Dom 模块
DOM 模块定义了分层的 FTXUI::Element 树,可用于构建复杂的终端界面,支持响应终端尺寸变化。 namespace ftxui {...// 定义文档 定义布局盒子 Element document vbox({// 设置文本 设置加粗 设置文本颜色text("The window") | bold | color(…...
SQL进阶之旅 Day 22:批处理与游标优化
【SQL进阶之旅 Day 22】批处理与游标优化 文章简述(300字左右) 在数据库开发中,面对大量数据的处理任务时,单条SQL语句往往无法满足性能需求。本篇文章聚焦“批处理与游标优化”,深入探讨如何通过批量操作和游标技术提…...
Java毕业设计:办公自动化系统的设计与实现
JAVA办公自动化系统 一、系统概述 本办公自动化系统基于Java EE平台开发,实现了企业日常办公的数字化管理。系统包含文档管理、流程审批、会议管理、日程安排、通讯录等核心功能模块,采用B/S架构设计,支持多用户协同工作。系统使用Spring B…...