矩阵距离——多源BFS
给定一个 N 行 M 列的 01 矩阵 A,A[i][j] 与 A[k][l] 之间的曼哈顿距离定义为:
dist(A[i][j],A[k][l])=|i−k|+|j−l|
输出一个 N 行 M 列的整数矩阵 B,其中:B[i][j]=min1≤x≤N,1≤y≤M,A[x][y]=1dist(A[i][j],A[x][y])
输入格式
第一行两个整数 N,M。接下来一个 N 行 M 列的 01 矩阵,数字之间没有空格。
输出格式
一个 N 行 M 列的矩阵 B,相邻两个整数之间用一个空格隔开。
数据范围
1≤N,M≤1000
输入样例:
3 4
0001
0011
0110
输出样例:
3 2 1 0
2 1 0 0
1 0 0 1
解析:
将 “1” 点放入队列,再遍历即可。不过要注意输入的问题,要用字符数组输入。
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ios ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
typedef pair<int,int> PII;
const int N=2e6+10;
char g[1010][1010];
int d[1010][1010];
bool vis[1010][1010];
int dx[4]={-1,1,0,0};
int dy[4]={0,0,-1,1};
int n,m;
queue <PII> q;
void bfs()
{for (int i=0;i<n;i++)for (int j=0;j<m;j++){if (g[i][j]=='1'){q.push({i,j});vis[i][j]=1;}}while (q.size()){int x=q.front().first;int y=q.front().second;q.pop();for (int i=0;i<4;i++){int a=x+dx[i],b=y+dy[i];if (a>=0&&a<n&&b>=0&&b<m&&!vis[a][b]){d[a][b]=d[x][y]+1;q.push({a,b});vis[a][b]=1;}}}
}
signed main()
{ios;cin>>n>>m;for (int i=0;i<n;i++) cin>>g[i];bfs();for (int i=0;i<n;i++){for (int j=0;j<m;j++) cout<<d[i][j]<<" ";cout<<endl;}return 0;
}
相关文章:
矩阵距离——多源BFS
给定一个 N 行 M 列的 01 矩阵 A,A[i][j] 与 A[k][l] 之间的曼哈顿距离定义为: dist(A[i][j],A[k][l])|i−k||j−l| 输出一个 N 行 M 列的整数矩阵 B,其中:B[i][j]min1≤x≤N,1≤y≤M,A[x][y]1dist(A[i][j],A[x][y]) 输入格式 第…...
关于在 Notion 中使用 Markdown 语法
关于在 Notion 中使用 Markdown 语法 习惯使用的 Markdown 的伙伴们应该知道,当需要加粗字体时,会首先输入 ** **,然后在里面填内容。 但是在 Notion 中,这个就不太行了。它所定义的规则是从前往后,也就是先键入**&…...
sigmoid和softmax函数有什么区别
Sigmoid函数和Softmax函数都是常用的激活函数,但它们的主要区别在于应用场景和输出结果的性质。 Sigmoid函数(也称为 Logistic函数): Sigmoid函数将输入值映射到0到1之间的连续实数范围,通常用于二元分类问题。 Si…...
第五章:最新版零基础学习 PYTHON 教程—Python 字符串操作指南(第七节 - Python 中使用 % 进行字符串格式化)
在Python中,可以通过不同的方法来实现对字符串所需的格式化。他们之中有一些是; 1) 使用 % 2) 使用 {} 3)使用模板字符串本文讨论使用 % 进行格式化。使用 % 的格式类似于 C 编程语言中的“printf”。%d – 整数 %f – 浮点数 %s – 字符串 %x – 十六进制 %o – 八进制 下面的…...
【网络安全 --- 工具安装】VMware 16.0 详细安装过程(提供资源)
一,VMware下载地址: 百度网盘链接链接:百度网盘 请输入提取码百度网盘为您提供文件的网络备份、同步和分享服务。空间大、速度快、安全稳固,支持教育网加速,支持手机端。注册使用百度网盘即可享受免费存储空间https:/…...
Eclipse MAT解析headp dump,total size小于file size
1. 问题描述 使用Eclipse MAT分析20GB的heap dump文件 最后解析出来dump size只有1GB 2. 原因:heap dump中包含许多unreachable objects Eclipse MAT的官方文档,《Basic Tutorial》章节,有对上图的Overview page做介绍 针对total size小…...
【数据挖掘】2022年 Quiz 1-3 整理 带答案
目录 Quiz 1Quiz 2Quiz 3Quiz 1 Problem 1 (50%). Consider the set of training data shown below. Here, A, B, C C C are attributes, and D D...
AcWing 288. 休息时间,《算法竞赛进阶指南》,环形与后效性处理
288. 休息时间 - AcWing题库 在某个星球上,一天由 N 个小时构成,我们称 0 点到 1 点为第 1 个小时、1 点到 2 点为第 2 个小时,以此类推。 在第 i 个小时睡觉能够恢复 Ui 点体力。 在这个星球上住着一头牛,它每天要休息 B 个小…...
一文掌握Linux系统信息查看命令(CPU、内存、进程、网口、磁盘、硬件)
引言 大家好,欢迎来到我的技术博客!如果你是一名Linux系统管理员、开发者或者热衷于学习Linux系统的用户,那么你一定需要掌握查看系统信息的命令。在这篇博客中,我将为你介绍一些常用的Linux命令,帮助你快速了解和监控…...
UE5.1编辑器拓展【三、脚本化资产行为,删除无引用资产】
目录 需要考虑的问题 重定向的修复函数 代码: 删除无引用资产 代码 需要添加的头文件和模块 在我们删除资产的时候,会发现,有些资产在删除的时候会出现有被什么什么引用,还有的是没有被引用。 而我们如果直接选择一片去进行…...
防抖和节流的实现
防抖和节流的实现 什么是防抖和节流实现防抖和节流防抖节流 防抖和节流的应用场景 什么是防抖和节流 防抖和节流是前端开发中常用的两种性能优化技术。 为什么需要防抖和节流呢? 两者目的都是为了防止某个时间段内操作频繁触发,造成性能消耗。 防抖&…...
alsa pcm接口之阻塞和非阻塞打开和异步通知模式
阻塞和非阻塞打开(Blocked and non-blocked open) 当设备打开在一个阻塞或非阻塞模式,ALSA pcm api接口使用不同的行为,模式可以指定通过mode参数通过snd_pcm_open函数,blocked mode阻塞模式是默认打开方式,在这个模式下,行为表现为当资源被其他应用程序使用,应该阻…...
Python Random模块详解
Random模块详解 随机数 random模块 randint(a, b) 返回[a, b]之间的整数randrange ([start,] stop [,step]) 从指定范围内,按指定基数递增的集合中获取一个随机数,基数 缺省值为1。random.randrange(1,7,2)choice(seq) 从非空序列的元素中随机挑选一个…...
Vue3 模糊搜索筛选
Vue3 模糊搜索筛选 环境: vue3 tselement plus 目标: 输入框输入内容,对展示的列表进行模糊搜索筛选匹配的内容。 代码如下: <div style"margin-top: 50px"><el-input v-model"valueInput" size&…...
【MVC】C# MVC基础知识点、原理以及容器和管道
给自己一个目标,然后坚持一段时间,总会有收获和感悟! 国庆假期马上结束,闲暇时间,重温一遍C#关于MVC的技术,控制器、视图、模型,知识点和原理,小伙伴们还记得吗 目录 一、MVC知识点1…...
【kubernetes】基于prometheus的监控
目录 1 监控解决方案2 prometheus2.1 容器监控2.2 节点监控2.3 资源对象监控2.4 metrics--server 3 prometheus-operator vs kube-prometheus vs helm3.1 prometheus-operator3.2 kube-prometheus3.3 helm 参考文档 1 监控解决方案 从实现方案来说,监控分为3个部分…...
Gmail 将停止支持基本 HTML 视图
根据 Google 支持文档的更新内容,Gmail 将从明年 1 月起停止支持基本 HTML 视图。 ▲ Gmai 基本 HTML 视图界面 目前网页版 Gmail 提供两个界面:基本 HTML 视图和标准视图。停止支持基本 HTML 视图后,当前打开经典模式的基本 HTML 视图模式 …...
电影大师杂记
假期集中刷了好多书,游戏和电影,在虚拟世界里猛烈的各种闲逛,cyberpunk 2077到blade runner,到异形,到终结者,到星球大战&环太平洋,到工业光魔,还有各种编程的书。。。 hmmm&…...
聊聊分布式架构——RPC通信原理
目录 RPC通信的基本原理 RPC结构 手撸简陋版RPC 知识点梳理 1.Socket套接字通信机制 2.通信过程的序列化与反序列化 3.动态代理 4.反射 思维流程梳理 码起来 服务端时序图 服务端—Api与Provider模块 客户端时序图 RPC通信的基本原理 RPC(Remote Proc…...
Android:实现手机前后摄像头预览同开
效果展示 一.概述 本博文讲解如何实现手机前后两颗摄像头同时预览并显示 我之前博文《OpenGLES:GLSurfaceView实现Android Camera预览》对单颗摄像头预览做过详细讲解,而前后双摄实现原理其实也并不复杂,粗糙点说就是把单摄像头预览流程写两…...
synchronized 学习
学习源: https://www.bilibili.com/video/BV1aJ411V763?spm_id_from333.788.videopod.episodes&vd_source32e1c41a9370911ab06d12fbc36c4ebc 1.应用场景 不超卖,也要考虑性能问题(场景) 2.常见面试问题: sync出…...
从深圳崛起的“机器之眼”:赴港乐动机器人的万亿赛道赶考路
进入2025年以来,尽管围绕人形机器人、具身智能等机器人赛道的质疑声不断,但全球市场热度依然高涨,入局者持续增加。 以国内市场为例,天眼查专业版数据显示,截至5月底,我国现存在业、存续状态的机器人相关企…...
【Redis技术进阶之路】「原理分析系列开篇」分析客户端和服务端网络诵信交互实现(服务端执行命令请求的过程 - 初始化服务器)
服务端执行命令请求的过程 【专栏简介】【技术大纲】【专栏目标】【目标人群】1. Redis爱好者与社区成员2. 后端开发和系统架构师3. 计算机专业的本科生及研究生 初始化服务器1. 初始化服务器状态结构初始化RedisServer变量 2. 加载相关系统配置和用户配置参数定制化配置参数案…...
五年级数学知识边界总结思考-下册
目录 一、背景二、过程1.观察物体小学五年级下册“观察物体”知识点详解:由来、作用与意义**一、知识点核心内容****二、知识点的由来:从生活实践到数学抽象****三、知识的作用:解决实际问题的工具****四、学习的意义:培养核心素养…...
Python爬虫(二):爬虫完整流程
爬虫完整流程详解(7大核心步骤实战技巧) 一、爬虫完整工作流程 以下是爬虫开发的完整流程,我将结合具体技术点和实战经验展开说明: 1. 目标分析与前期准备 网站技术分析: 使用浏览器开发者工具(F12&…...
c#开发AI模型对话
AI模型 前面已经介绍了一般AI模型本地部署,直接调用现成的模型数据。这里主要讲述讲接口集成到我们自己的程序中使用方式。 微软提供了ML.NET来开发和使用AI模型,但是目前国内可能使用不多,至少实践例子很少看见。开发训练模型就不介绍了&am…...
MySQL中【正则表达式】用法
MySQL 中正则表达式通过 REGEXP 或 RLIKE 操作符实现(两者等价),用于在 WHERE 子句中进行复杂的字符串模式匹配。以下是核心用法和示例: 一、基础语法 SELECT column_name FROM table_name WHERE column_name REGEXP pattern; …...
ArcGIS Pro制作水平横向图例+多级标注
今天介绍下载ArcGIS Pro中如何设置水平横向图例。 之前我们介绍了ArcGIS的横向图例制作:ArcGIS横向、多列图例、顺序重排、符号居中、批量更改图例符号等等(ArcGIS出图图例8大技巧),那这次我们看看ArcGIS Pro如何更加快捷的操作。…...
优选算法第十二讲:队列 + 宽搜 优先级队列
优选算法第十二讲:队列 宽搜 && 优先级队列 1.N叉树的层序遍历2.二叉树的锯齿型层序遍历3.二叉树最大宽度4.在每个树行中找最大值5.优先级队列 -- 最后一块石头的重量6.数据流中的第K大元素7.前K个高频单词8.数据流的中位数 1.N叉树的层序遍历 2.二叉树的锯…...
Springboot社区养老保险系统小程序
一、前言 随着我国经济迅速发展,人们对手机的需求越来越大,各种手机软件也都在被广泛应用,但是对于手机进行数据信息管理,对于手机的各种软件也是备受用户的喜爱,社区养老保险系统小程序被用户普遍使用,为方…...
