当前位置: 首页 > 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…...

大数据零基础学习day1之环境准备和大数据初步理解

学习大数据会使用到多台Linux服务器。 一、环境准备 1、VMware 基于VMware构建Linux虚拟机 是大数据从业者或者IT从业者的必备技能之一也是成本低廉的方案 所以VMware虚拟机方案是必须要学习的。 &#xff08;1&#xff09;设置网关 打开VMware虚拟机&#xff0c;点击编辑…...

OpenPrompt 和直接对提示词的嵌入向量进行训练有什么区别

OpenPrompt 和直接对提示词的嵌入向量进行训练有什么区别 直接训练提示词嵌入向量的核心区别 您提到的代码: prompt_embedding = initial_embedding.clone().requires_grad_(True) optimizer = torch.optim.Adam([prompt_embedding...

FFmpeg:Windows系统小白安装及其使用

一、安装 1.访问官网 Download FFmpeg 2.点击版本目录 3.选择版本点击安装 注意这里选择的是【release buids】&#xff0c;注意左上角标题 例如我安装在目录 F:\FFmpeg 4.解压 5.添加环境变量 把你解压后的bin目录&#xff08;即exe所在文件夹&#xff09;加入系统变量…...

DBLP数据库是什么?

DBLP&#xff08;Digital Bibliography & Library Project&#xff09;Computer Science Bibliography是全球著名的计算机科学出版物的开放书目数据库。DBLP所收录的期刊和会议论文质量较高&#xff0c;数据库文献更新速度很快&#xff0c;很好地反映了国际计算机科学学术研…...

数据结构第5章:树和二叉树完全指南(自整理详细图文笔记)

名人说&#xff1a;莫道桑榆晚&#xff0c;为霞尚满天。——刘禹锡&#xff08;刘梦得&#xff0c;诗豪&#xff09; 原创笔记&#xff1a;Code_流苏(CSDN)&#xff08;一个喜欢古诗词和编程的Coder&#x1f60a;&#xff09; 上一篇&#xff1a;《数据结构第4章 数组和广义表》…...

C# winform教程(二)----checkbox

一、作用 提供一个用户选择或者不选的状态&#xff0c;这是一个可以多选的控件。 二、属性 其实功能大差不差&#xff0c;除了特殊的几个外&#xff0c;与button基本相同&#xff0c;所有说几个独有的 checkbox属性 名称内容含义appearance控件外观可以变成按钮形状checkali…...

命令行关闭Windows防火墙

命令行关闭Windows防火墙 引言一、防火墙:被低估的"智能安检员"二、优先尝试!90%问题无需关闭防火墙方案1:程序白名单(解决软件误拦截)方案2:开放特定端口(解决网游/开发端口不通)三、命令行极速关闭方案方法一:PowerShell(推荐Win10/11)​方法二:CMD命令…...

boost::filesystem::path文件路径使用详解和示例

boost::filesystem::path 是 Boost 库中用于跨平台操作文件路径的类&#xff0c;封装了路径的拼接、分割、提取、判断等常用功能。下面是对它的使用详解&#xff0c;包括常用接口与完整示例。 1. 引入头文件与命名空间 #include <boost/filesystem.hpp> namespace fs b…...

Copilot for Xcode (iOS的 AI辅助编程)

Copilot for Xcode 简介Copilot下载与安装 体验环境要求下载最新的安装包安装登录系统权限设置 AI辅助编程生成注释代码补全简单需求代码生成辅助编程行间代码生成注释联想 代码生成 总结 简介 尝试使用了Copilot&#xff0c;它能根据上下文补全代码&#xff0c;快速生成常用…...

PLC入门【4】基本指令2(SET RST)

04 基本指令2 PLC编程第四课基本指令(2) 1、运用上接课所学的基本指令完成个简单的实例编程。 2、学习SET--置位指令 3、RST--复位指令 打开软件(FX-TRN-BEG-C)&#xff0c;从 文件 - 主画面&#xff0c;“B: 让我们学习基本的”- “B-3.控制优先程序”。 点击“梯形图编辑”…...