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

龙虎榜——20250610

上证指数放量收阴线&#xff0c;个股多数下跌&#xff0c;盘中受消息影响大幅波动。 深证指数放量收阴线形成顶分型&#xff0c;指数短线有调整的需求&#xff0c;大概需要一两天。 2025年6月10日龙虎榜行业方向分析 1. 金融科技 代表标的&#xff1a;御银股份、雄帝科技 驱动…...

7.4.分块查找

一.分块查找的算法思想&#xff1a; 1.实例&#xff1a; 以上述图片的顺序表为例&#xff0c; 该顺序表的数据元素从整体来看是乱序的&#xff0c;但如果把这些数据元素分成一块一块的小区间&#xff0c; 第一个区间[0,1]索引上的数据元素都是小于等于10的&#xff0c; 第二…...

C++_核心编程_多态案例二-制作饮品

#include <iostream> #include <string> using namespace std;/*制作饮品的大致流程为&#xff1a;煮水 - 冲泡 - 倒入杯中 - 加入辅料 利用多态技术实现本案例&#xff0c;提供抽象制作饮品基类&#xff0c;提供子类制作咖啡和茶叶*//*基类*/ class AbstractDr…...

【kafka】Golang实现分布式Masscan任务调度系统

要求&#xff1a; 输出两个程序&#xff0c;一个命令行程序&#xff08;命令行参数用flag&#xff09;和一个服务端程序。 命令行程序支持通过命令行参数配置下发IP或IP段、端口、扫描带宽&#xff0c;然后将消息推送到kafka里面。 服务端程序&#xff1a; 从kafka消费者接收…...

通过Wrangler CLI在worker中创建数据库和表

官方使用文档&#xff1a;Getting started Cloudflare D1 docs 创建数据库 在命令行中执行完成之后&#xff0c;会在本地和远程创建数据库&#xff1a; npx wranglerlatest d1 create prod-d1-tutorial 在cf中就可以看到数据库&#xff1a; 现在&#xff0c;您的Cloudfla…...

关于nvm与node.js

1 安装nvm 安装过程中手动修改 nvm的安装路径&#xff0c; 以及修改 通过nvm安装node后正在使用的node的存放目录【这句话可能难以理解&#xff0c;但接着往下看你就了然了】 2 修改nvm中settings.txt文件配置 nvm安装成功后&#xff0c;通常在该文件中会出现以下配置&…...

Objective-C常用命名规范总结

【OC】常用命名规范总结 文章目录 【OC】常用命名规范总结1.类名&#xff08;Class Name)2.协议名&#xff08;Protocol Name)3.方法名&#xff08;Method Name)4.属性名&#xff08;Property Name&#xff09;5.局部变量/实例变量&#xff08;Local / Instance Variables&…...

鱼香ros docker配置镜像报错:https://registry-1.docker.io/v2/

使用鱼香ros一件安装docker时的https://registry-1.docker.io/v2/问题 一键安装指令 wget http://fishros.com/install -O fishros && . fishros出现问题&#xff1a;docker pull 失败 网络不同&#xff0c;需要使用镜像源 按照如下步骤操作 sudo vi /etc/docker/dae…...

【python异步多线程】异步多线程爬虫代码示例

claude生成的python多线程、异步代码示例&#xff0c;模拟20个网页的爬取&#xff0c;每个网页假设要0.5-2秒完成。 代码 Python多线程爬虫教程 核心概念 多线程&#xff1a;允许程序同时执行多个任务&#xff0c;提高IO密集型任务&#xff08;如网络请求&#xff09;的效率…...

Swagger和OpenApi的前世今生

Swagger与OpenAPI的关系演进是API标准化进程中的重要篇章&#xff0c;二者共同塑造了现代RESTful API的开发范式。 本期就扒一扒其技术演进的关键节点与核心逻辑&#xff1a; &#x1f504; 一、起源与初创期&#xff1a;Swagger的诞生&#xff08;2010-2014&#xff09; 核心…...