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

173. 矩阵距离 acwing -多路BFS

原题链接:173. 矩阵距离 - AcWing题库

给定一个 N行 M 列的 01矩阵 A,A[i][j] 与 A[k][l]]之间的曼哈顿距离定义为:

dist(i,j,k,l)=|i−k|+|j−l||

输出一个 N 行 M 列的整数矩阵 B,其中:

B[i][j]=min1≤x≤N,1≤y≤M,A[x][y]=1dist(i,j,x,y)

输入格式

第一行两个整数 N,M

接下来一个 N 行 M 列的 01 矩阵,数字之间没有空格。

输出格式

一个 NN 行 MM 列的矩阵 B,相邻两个整数之间用一个空格隔开。

数据范围

1≤N,M≤1000

输入样例:
3 4
0001
0011
0110
输出样例:
3 2 1 0
2 1 0 0
1 0 0 1

#include<iostream>
#include<algorithm>
#include<cstring>// 定义宏,方便使用pair的first和second成员
#define x first
#define y secondusing namespace std;// 定义一个pair<int, int>类型的别名PII
typedef pair<int,int> PII;// 定义常量N和M,N表示网格的最大行数,M表示队列的最大大小
const int N = 1010, M = N*N;// 定义全局变量n和m,分别表示网格的行数和列数
int n, m;// 定义一个二维字符数组g,用于存储网格中的字符
char g[N][N];// 定义一个队列q,用于广度优先搜索
PII q[M];// 定义一个二维整数数组dist,用于存储每个位置到最近的'1'的距离
int dist[N][N];// 定义广度优先搜索函数bfs
void bfs()
{// 初始化dist数组,所有位置的距离设为-1memset(dist, -1, sizeof dist);// 定义队列的头指针hh和尾指针ttint hh = 0, tt = -1;// 遍历整个网格,将所有值为'1'的位置加入队列,并将它们的距离设为0for (int i = 0; i < n; i++){for (int j = 0; j < m; j++){if (g[i][j] == '1'){dist[i][j] = 0;q[++tt] = {i, j};}}}// 定义四个方向的移动数组dx和dyint dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};// 开始广度优先搜索while (hh <= tt){// 取出队列头部元素auto t = q[hh++];// 遍历四个方向for (int i = 0; i < 4; i++){// 计算新位置的坐标int a = t.x + dx[i], b = t.y + dy[i];// 如果新位置超出网格范围,则跳过if (a < 0 || a >= n || b < 0 || b >= m) continue;// 如果新位置已经访问过,则跳过if (dist[a][b] != -1) continue;// 更新新位置的距离,并将其加入队列dist[a][b] = dist[t.x][t.y] + 1;q[++tt] = {a, b};}}
}// 主函数
int main()
{// 读取网格的行数和列数scanf("%d %d", &n, &m);// 读取网格中的字符for (int i = 0; i < n; i++){scanf("%s", g[i]);}// 调用广度优先搜索函数bfs();// 输出每个位置到最近的'1'的距离for (int i = 0; i < n; i++){for (int j = 0; j < m; j++){printf("%d ", dist[i][j]);}printf("\n");}return 0;
}

相关文章:

173. 矩阵距离 acwing -多路BFS

原题链接&#xff1a;173. 矩阵距离 - AcWing题库 给定一个 N行 M 列的 01矩阵 A&#xff0c;A[i][j] 与 A[k][l]]之间的曼哈顿距离定义为&#xff1a; dist(i,j,k,l)|i−k||j−l|| 输出一个 N 行 M 列的整数矩阵 B&#xff0c;其中&#xff1a; B[i][j]min1≤x≤N,1≤y≤M,A…...

Linux下部署Redis集群 - 一主二从三哨兵模式

三台服务器redis一主二从三哨兵模式搭建 最近使用到了redis集群部署&#xff0c;使用一主二从三哨兵集群部署redis&#xff0c;将自己部署的过程中的使用心得分享给大家&#xff0c;希望大家以后部署的过程减少一些坑。 服务器准备 3台服务器 &#xff0c;确定主redis和从red…...

实战设计模式之建造者模式

概述 在实际项目中&#xff0c;我们有时会遇到需要创建复杂对象的情况。这些对象可能包含多个组件或属性&#xff0c;而且每个组件都有自己的配置选项。如果直接使用构造函数或前面介绍的工厂方法来创建这样的对象&#xff0c;可能会导致以下两个严重问题。 1、参数过多。当一个…...

活动预告 | Microsoft Azure 在线技术公开课:使用 Azure OpenAI 服务构建生成式应用

课程介绍 通过 Microsoft Learn 免费参加 Microsoft Azure 在线技术公开课&#xff0c;掌握创造新机遇所需的技能&#xff0c;加快对 Microsoft Cloud 技术的了解。参加我们举办的“使用 Azure OpenAI 服务构建生成式应用”活动&#xff0c;了解如何使用包括 GPT 在内的强大的…...

ubuntu安装firefox

firefox下载地址&#xff1a;https://ftp.mozilla.org/pub/firefox/releases/ 卸载 sudo apt-get update dpkg --get-selections |grep firefox apt-get purge firefox 解压 tar -xjf firefox*.tar.bz2复制文件 sudo mv firefox/ /opt/firefox30sudo mv /usr/bin/firefox /…...

计算机网络原理(谢希仁第八版)第4章课后习题答案

第四章 网络层 详细计算机网络&#xff08;谢希仁-第八版&#xff09;第四章习题全解_计算机网络第八版谢希仁课后答案-CSDN博客 1.网络层向上提供的服务有哪两种&#xff1f;是比较其优缺点。网络层向运输层提供 “面向连接”虚电路&#xff08;Virtual Circuit&#xff09;服…...

RabbitMQ-基本使用

RabbitMQ: One broker to queue them all | RabbitMQ 官方 安装到Docker中 docker run \-e RABBITMQ_DEFAULT_USERrabbit \-e RABBITMQ_DEFAULT_PASSrabbit \-v mq-plugins:/plugins \--name mq \--hostname mq \-p 15672:15672 \-p 5672:5672 \--network mynet\-d \rabbitmq:3…...

从零开始学架构——互联网架构的演进

1 技术演进 1.1 技术演进的动力 对于新技术&#xff0c;我们应该站在行业的角度上思考&#xff0c;哪些技术我们要采取&#xff0c;哪些技术我们不能用&#xff0c;投入成本过大会不会导致满盘皆输&#xff1f;市场、技术、管理三者组成的业务发展铁三角&#xff0c;任何一个…...

python +tkinter绘制彩虹和云朵

python tkinter绘制彩虹和云朵 彩虹&#xff0c;简称虹&#xff0c;是气象中的一种光学现象&#xff0c;当太阳光照射到半空中的水滴&#xff0c;光线被折射及反射&#xff0c;在天空上形成拱形的七彩光谱&#xff0c;由外圈至内圈呈红、橙、黄、绿、蓝、靛、紫七种颜色。事实…...

重新整理机器学习和神经网络框架

本篇重新梳理了人工智能&#xff08;AI&#xff09;、机器学习&#xff08;ML&#xff09;、神经网络&#xff08;NN&#xff09;和深度学习&#xff08;DL&#xff09;之间存在一定的包含关系&#xff0c;以下是它们的关系及各自内容,以及人工智能领域中深度学习分支对比整理。…...

TypyScript从入门到精通

TypyScript从入门到精通 TypyScript 是什么&#xff1f;增加了什么环境搭建二、为何需要 TypeScript三、编译 TypeScript四、类型声明五、类型推断基本类型六、类型总览JavaScript 中的数据类型TypeScript 中的数据类型1. 上述所有 JavaScript 类型2. 六个新类型&#xff1a;3.…...

【MATLAB】绘制投资组合的有效前沿

文章目录 一、数据准备二、有效前沿三、代码3.1 数据批量读取、预处理3.2 绘制可行集3.3 绘制有效前沿3.4 其它-最大夏普率 一、数据准备 准备多个股票的的历史数据&#xff0c;目的就是找到最优的投资组合。 下载几个标普500里面的公式的股票数据吧&#xff0c;下载方法也可…...

matlab时频分析库

time frequency gallery...

GBase 8s 数据库备份还原

每一天都是一个新的篇章&#xff0c;等待着你去书写属于自己的故事&#xff01;&#xff01;&#xff01; 一&#xff1a;备份 1.1.下载脚本文件&#xff0c;并上传到数据库服务器上相应目录。 解压后目录为&#xff1a; 说明&#xff1a; dbcomm.sh&#xff1a;导出注释脚本…...

C++模板相关概念汇总

文章目录 一、模板的概念与作用二、函数模板模板的非类型参数调用顺序 三、类模板四、模板的编译模型 一、模板的概念与作用 C模板是一种强大的代码复用机制&#xff0c;它允许程序员编写通用的代码&#xff0c;能够处理不同类型的数据&#xff0c;而无需为每种类型都重复编写…...

MYSQL------sql基础

SQL基础与简介 定义&#xff1a;SQL即结构化查询语言&#xff08;Structured Query Language&#xff09;&#xff0c;是一种特殊目的的编程语言&#xff0c;用于存取数据以及查询、更新和管理关系数据库系统。作用&#xff1a;可以用于数据库的创建、数据的插入、查询、更新和…...

React Router 用法概览

React Router 用法 React 使得开发者能够轻松地创建交互式的单页应用&#xff08;SPA&#xff09;&#xff0c;单页应用的一个常见挑战是如何处理页面导航和路由吗&#xff0c;React Router 就是解决这个问题的工具 路由&#xff08;Router&#xff09;是 React Router 的核心…...

网络安全之高防IP的实时监控精准防护

高防IP是一种网络安全设备&#xff0c;用于保护网络服务不受到各类攻击的影响&#xff0c;确保业务的持续稳定运行。它通过监控、识别和封锁恶意攻击流量&#xff0c;提供高级别的防护&#xff0c;降低业务被攻击的风险&#xff0c;并提升网络的稳定性和可靠性。 一、实时监控的…...

2024年中国新能源汽车用车发展怎么样 PaperGPT(二)

用车趋势深入分析 接上文&#xff0c;2024年中国新能源汽车用车发展怎么样 PaperGPT&#xff08;一&#xff09;-CSDN博客本文将继续深入探讨新能源汽车的用车强度、充电行为以及充电设施的现状。 用车强度 月均行驶里程&#xff1a;2024年纯电车辆月均行驶超过1500公里&…...

LINUXC 时间相关操作

文章目录 时间戳获取本地时间struct tm 结构体高精度的时间struct timeval 结构体相关函数time()localtime()gmtime()gettimeofday()strftime()mktime() 示例代码 时间戳 时间戳是指计算机中存储的数字型时间。它是以一个特定的时间点作为起点&#xff08;通常是1970年1月1日0…...

【Axure高保真原型】引导弹窗

今天和大家中分享引导弹窗的原型模板&#xff0c;载入页面后&#xff0c;会显示引导弹窗&#xff0c;适用于引导用户使用页面&#xff0c;点击完成后&#xff0c;会显示下一个引导弹窗&#xff0c;直至最后一个引导弹窗完成后进入首页。具体效果可以点击下方视频观看或打开下方…...

Android Wi-Fi 连接失败日志分析

1. Android wifi 关键日志总结 (1) Wi-Fi 断开 (CTRL-EVENT-DISCONNECTED reason3) 日志相关部分&#xff1a; 06-05 10:48:40.987 943 943 I wpa_supplicant: wlan0: CTRL-EVENT-DISCONNECTED bssid44:9b:c1:57:a8:90 reason3 locally_generated1解析&#xff1a; CTR…...

iOS 26 携众系统重磅更新,但“苹果智能”仍与国行无缘

美国西海岸的夏天&#xff0c;再次被苹果点燃。一年一度的全球开发者大会 WWDC25 如期而至&#xff0c;这不仅是开发者的盛宴&#xff0c;更是全球数亿苹果用户翘首以盼的科技春晚。今年&#xff0c;苹果依旧为我们带来了全家桶式的系统更新&#xff0c;包括 iOS 26、iPadOS 26…...

基于ASP.NET+ SQL Server实现(Web)医院信息管理系统

医院信息管理系统 1. 课程设计内容 在 visual studio 2017 平台上&#xff0c;开发一个“医院信息管理系统”Web 程序。 2. 课程设计目的 综合运用 c#.net 知识&#xff0c;在 vs 2017 平台上&#xff0c;进行 ASP.NET 应用程序和简易网站的开发&#xff1b;初步熟悉开发一…...

【Redis技术进阶之路】「原理分析系列开篇」分析客户端和服务端网络诵信交互实现(服务端执行命令请求的过程 - 初始化服务器)

服务端执行命令请求的过程 【专栏简介】【技术大纲】【专栏目标】【目标人群】1. Redis爱好者与社区成员2. 后端开发和系统架构师3. 计算机专业的本科生及研究生 初始化服务器1. 初始化服务器状态结构初始化RedisServer变量 2. 加载相关系统配置和用户配置参数定制化配置参数案…...

前端导出带有合并单元格的列表

// 导出async function exportExcel(fileName "共识调整.xlsx") {// 所有数据const exportData await getAllMainData();// 表头内容let fitstTitleList [];const secondTitleList [];allColumns.value.forEach(column > {if (!column.children) {fitstTitleL…...

376. Wiggle Subsequence

376. Wiggle Subsequence 代码 class Solution { public:int wiggleMaxLength(vector<int>& nums) {int n nums.size();int res 1;int prediff 0;int curdiff 0;for(int i 0;i < n-1;i){curdiff nums[i1] - nums[i];if( (prediff > 0 && curdif…...

【CSS position 属性】static、relative、fixed、absolute 、sticky详细介绍,多层嵌套定位示例

文章目录 ★ position 的五种类型及基本用法 ★ 一、position 属性概述 二、position 的五种类型详解(初学者版) 1. static(默认值) 2. relative(相对定位) 3. absolute(绝对定位) 4. fixed(固定定位) 5. sticky(粘性定位) 三、定位元素的层级关系(z-i…...

GitHub 趋势日报 (2025年06月08日)

&#x1f4ca; 由 TrendForge 系统生成 | &#x1f310; https://trendforge.devlive.org/ &#x1f310; 本日报中的项目描述已自动翻译为中文 &#x1f4c8; 今日获星趋势图 今日获星趋势图 884 cognee 566 dify 414 HumanSystemOptimization 414 omni-tools 321 note-gen …...

JVM暂停(Stop-The-World,STW)的原因分类及对应排查方案

JVM暂停(Stop-The-World,STW)的完整原因分类及对应排查方案,结合JVM运行机制和常见故障场景整理而成: 一、GC相关暂停​​ 1. ​​安全点(Safepoint)阻塞​​ ​​现象​​:JVM暂停但无GC日志,日志显示No GCs detected。​​原因​​:JVM等待所有线程进入安全点(如…...