矩阵距离——多源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预览》对单颗摄像头预览做过详细讲解,而前后双摄实现原理其实也并不复杂,粗糙点说就是把单摄像头预览流程写两…...
网络六边形受到攻击
大家读完觉得有帮助记得关注和点赞!!! 抽象 现代智能交通系统 (ITS) 的一个关键要求是能够以安全、可靠和匿名的方式从互联车辆和移动设备收集地理参考数据。Nexagon 协议建立在 IETF 定位器/ID 分离协议 (…...
抖音增长新引擎:品融电商,一站式全案代运营领跑者
抖音增长新引擎:品融电商,一站式全案代运营领跑者 在抖音这个日活超7亿的流量汪洋中,品牌如何破浪前行?自建团队成本高、效果难控;碎片化运营又难成合力——这正是许多企业面临的增长困局。品融电商以「抖音全案代运营…...
镜像里切换为普通用户
如果你登录远程虚拟机默认就是 root 用户,但你不希望用 root 权限运行 ns-3(这是对的,ns3 工具会拒绝 root),你可以按以下方法创建一个 非 root 用户账号 并切换到它运行 ns-3。 一次性解决方案:创建非 roo…...
【Web 进阶篇】优雅的接口设计:统一响应、全局异常处理与参数校验
系列回顾: 在上一篇中,我们成功地为应用集成了数据库,并使用 Spring Data JPA 实现了基本的 CRUD API。我们的应用现在能“记忆”数据了!但是,如果你仔细审视那些 API,会发现它们还很“粗糙”:有…...
Caliper 配置文件解析:config.yaml
Caliper 是一个区块链性能基准测试工具,用于评估不同区块链平台的性能。下面我将详细解释你提供的 fisco-bcos.json 文件结构,并说明它与 config.yaml 文件的关系。 fisco-bcos.json 文件解析 这个文件是针对 FISCO-BCOS 区块链网络的 Caliper 配置文件,主要包含以下几个部…...
服务器--宝塔命令
一、宝塔面板安装命令 ⚠️ 必须使用 root 用户 或 sudo 权限执行! sudo su - 1. CentOS 系统: yum install -y wget && wget -O install.sh http://download.bt.cn/install/install_6.0.sh && sh install.sh2. Ubuntu / Debian 系统…...
站群服务器的应用场景都有哪些?
站群服务器主要是为了多个网站的托管和管理所设计的,可以通过集中管理和高效资源的分配,来支持多个独立的网站同时运行,让每一个网站都可以分配到独立的IP地址,避免出现IP关联的风险,用户还可以通过控制面板进行管理功…...
【 java 虚拟机知识 第一篇 】
目录 1.内存模型 1.1.JVM内存模型的介绍 1.2.堆和栈的区别 1.3.栈的存储细节 1.4.堆的部分 1.5.程序计数器的作用 1.6.方法区的内容 1.7.字符串池 1.8.引用类型 1.9.内存泄漏与内存溢出 1.10.会出现内存溢出的结构 1.内存模型 1.1.JVM内存模型的介绍 内存模型主要分…...
前端中slice和splic的区别
1. slice slice 用于从数组中提取一部分元素,返回一个新的数组。 特点: 不修改原数组:slice 不会改变原数组,而是返回一个新的数组。提取数组的部分:slice 会根据指定的开始索引和结束索引提取数组的一部分。不包含…...
深入浅出Diffusion模型:从原理到实践的全方位教程
I. 引言:生成式AI的黎明 – Diffusion模型是什么? 近年来,生成式人工智能(Generative AI)领域取得了爆炸性的进展,模型能够根据简单的文本提示创作出逼真的图像、连贯的文本,乃至更多令人惊叹的…...
