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

[BFS] 广度优先搜索

 1. 数字操作

常见的模板

// 使用一个数组判断元素是否入过队
int inqueue[N] = {0};

// 层数或者可以称为深度
int step = 0;
// 判断是否可以入队的条件
int isvalid(){
    
}

BFS(int x){
    // 将初始的元素压入队列
    // 注意每次压队的时候都要将inque[x] = 1,表明入队过
    queue<int> q;
    q.push(x);
    inqueue[x] = 1;

    //大循环 队列q不为空
    while (!q.empty()){
        // 获得这一层的所有元素 ,因为咱们是广度优先
        int cnt = q.size();
        
        //小循环
        while (cnt--){
        int temp = q.front();
        q.pop();
        
        // BFS寻找的目的,这里就是temp 是否 == n
        if (temp == n){
            return ;//视情况而定
        }
        
        // 以此节点开始寻找下一层的有效节点
        if (isvalid(temp+1)){
            q.push(temp+1);
            // 注意压队就要伴随着inqueue[]的变化
            inqueue[temp+1] = 1;
        }
        // ....同理 
    }
    // 在小循环结束后,意味着整层的元素都被遍历过了,若没有,则下一层
    step++;
    }
}

#include <cstdio>
#include <queue>
using namespace std;
const int N = 1e5+10;
int n;
int inqueue[N] = {0};
int isvalid(int x){if (x<=n && inqueue[x] == 0)return 1;else return 0;
}
int step = 0;
void BFS(){   queue<int> q;q.push(1);inqueue[1] = 1;while (!q.empty()){int cnt = q.size();while (cnt--){int temp = q.front();q.pop();if (temp == n){return;}if (isvalid(temp+1)){q.push(temp+1);inqueue[temp+1] = 1;}if (isvalid(temp*2)){q.push(temp*2);inqueue[temp*2] = 1;}}step++;}
}
int main(){scanf("%d",&n);BFS();printf("%d",step);return 0;
}

2. 矩阵的块 

题目的思路很简单,首先就是从头到尾遍历数组,当遇到1并且未如过队(证明其是一个全新的块)时进行BFS,直到周围都是0无法进展为止,在BFS过程中,遍历过的1都被压入队中,因此inqueue为1,那么经过几次BFS,证明就有几个块。

#include <cstdio>
#include <queue>
#include <utility>using namespace std;
// 由于需要压队,那么队内的元素为PII
typedef pair<int,int> PII;const int N = 110;
int n,m;
// 是否入队,位置用二维数组即可
int inqueue[N][N] = {0};// 存储整个矩阵
int A[N][N];// 块的数量
int count = 0;// 为了便于上下左右的移动,可以设置两个数组,表示上下左右的变量
int dx[4] = {-1,1,0,0};
int dy[4] = {0,0,-1,1};int isvalid(int x,int y){// 有效的压队条件,x,y未逾越矩阵的范围,未入过队,并且值为1if (x>=1 && x<=n && y>=1 && y<=m && inqueue[x][y] == 0 && A[x][y] == 1)return 1;else return 0; 
}
void BFS(int i,int j){queue<PII> q;q.push(make_pair(i,j));inqueue[i][j] = 1;while (!q.empty()){int cnt = q.size();while (cnt--){PII temp = q.front();q.pop();// 我们无需返回什么,因此这里不需要写return 的语句// 开始寻找下一个有效的节点for (int i=0;i<4;i++){int nextx = temp.first+dx[i];int nexty = temp.second+dy[i];if (isvalid(nextx,nexty)){q.push(make_pair(nextx,nexty));inqueue[nextx][nexty] = 1;}}}}
}
int main(){scanf("%d%d",&n,&m);for (int i=1;i<=n;i++)for (int j=1;j<=m;j++)scanf("%d",&A[i][j]);for (int i=1;i<=n;i++)for (int j=1;j<=m;j++)if (A[i][j] == 1 && inqueue[i][j] == 0){BFS(i,j);count++;}printf("%d",count);return 0;
}

相关文章:

[BFS] 广度优先搜索

1. 数字操作 常见的模板 // 使用一个数组判断元素是否入过队 int inqueue[N] {0}; // 层数或者可以称为深度 int step 0; // 判断是否可以入队的条件 int isvalid(){ } BFS(int x){ // 将初始的元素压入队列 // 注意每次压队的时候都要将inque[x] 1,表明入队过…...

蓝桥杯官网填空题(矩形切割)

题目描述 本题为填空题&#xff0c;只需要算出结果后&#xff0c;在代码中使用输出语句将所填结果输出即可。 小明有一些矩形的材料&#xff0c;他要从这些矩形材料中切割出一些正方形。 当他面对一块矩形材料时&#xff0c;他总是从中间切割一刀&#xff0c;切出一块最大的…...

通过Docker Compose安装MQTT

一、文件和目录说明 1、MQTT安装时的文件和目录 EMQX 安装完成后会创建一些目录用来存放运行文件和配置文件&#xff0c;存储数据以及记录日志。 不同安装方式得到的文件和目录位置有所不同&#xff0c;具体如下&#xff1a; 注意&#xff1a; 压缩包解压安装时&#xff0c;目…...

Golang企业面试题

Golang企业面试题 基础 高级 Golang有哪些优势&#xff1f;Golang数据类型有哪些Golang中的包如何使用Go 支持什么形式的类型转换&#xff1f;什么是 Goroutine&#xff1f;你如何停止它&#xff1f;如何在运行时检查变量类型&#xff1f;Go 两个接口之间可以存在什么关系&a…...

Jenkins测试报告样式优化

方式一&#xff1a;修改Content Security Policy&#xff08;临时解决&#xff0c;Jenkins重启后失效) 1、jenkins首页—>ManageJenkins—>Tools and Actions标题下—>Script Console 2、粘贴脚本输入框中&#xff1a;System.setProperty("hudson.model.Directo…...

函数相关概念

4.函数 1.函数的概念 1.什么是函数? 把特点的代码片段,抽取成为独立运行的实体 2.使用函数的好处1.重复使用,提供效率2.提高代码的可读性3.有利用程序的维护 3.函数的分类1.内置函数(系统函数)已经提高的alert(); prompt();confirm();print()document.write(),console.log()…...

2023软考学习营

...

Vue2进阶篇学习笔记

文章目录 Vue2进阶学习笔记前言1、Vue脚手架学习1.1 Vue脚手架概述1.2 Vue脚手架安装1.3 常用属性1.4 插件 2、组件基本概述3、非单文件组件3.1 非单文件组件的基本使用3.2 组件的嵌套 4、单文件组件4.1 快速体验4.2 Todo案例 5、浏览器本地存储6、组件的自定义事件6.1 使用自定…...

Python 正则表达式:强大的文本处理工具

概念&#xff1a; 正则表达式是一种强大的文本匹配和处理工具&#xff0c;它可以用来在字符串中查找、替换和提取符合某种规则的内容。在Python中&#xff0c;使用re模块可以轻松地操作正则表达式&#xff0c;它提供了丰富的功能和灵活的语法。 场景&#xff1a; 正则表达式…...

Linux如何查看系统时间

文章目录 一、使用date命令查看系统时间二、通过/var/log/syslog文件查看系统时间三、通过/proc/uptime文件查看系统运行时间四、通过hwclock命令查看硬件时间五、通过timedatectl命令设置系统时区六、通过NTP协议同步网络时间七、通过ntpstat命令检查NTP同步状态八、使用cal命…...

46. 出勤率问题

文章目录 题目需求实现一题目来源 题目需求 现有用户出勤表&#xff08;user_login&#xff09;如下。 user_id (用户id)course_id (课程id)login_in &#xff08;登录时间&#xff09;login_out &#xff08;登出时间&#xff09;112022-06-02 09:08:242022-06-02 10:09:361…...

Xilinx IDDR与ODDR原语的使用

文章目录 ODDR原语1. OPPOSITE_EDGE 模式2. SAME_EDGE 模式 ODDR原语 例化模板&#xff1a; ODDR #(.DDR_CLK_EDGE("OPPOSITE_EDGE"), // "OPPOSITE_EDGE" or "SAME_EDGE" .INIT(1b0), // Initial value of Q: 1b0 or 1b1.SRTYPE("SYNC…...

面试系列 - 序列化和反序列化详解

Java 序列化是一种将对象转换为字节流的过程&#xff0c;可以将对象的状态保存到磁盘文件或通过网络传输。反序列化则是将字节流重新转换为对象的过程。Java 提供了一个强大的序列化框架&#xff0c;允许你在对象的持久化和网络通信中使用它。 一、Java 序列化的基本原理 Jav…...

基于Elasticsearch + Fluentd + Kibana(EFK)搭建日志收集管理系统

目录 1、EFK简介 2、EFK框架 2.1、Fluentd系统架构 2.2、Elasticsearch系统架构 2.3、Kibana系统架构 3、Elasticsearch接口 4、EFK在虚拟机中安装步骤 4.1、安装elasticsearch 4.2、安装kibana 4.3、安装fluentd 4.4、进入kibana创建索引 5、Fluentd配置介绍 VC常…...

【Python小项目之Tkinter应用】解决Python的Pyinstaller将.py文件打包成.exe可执行文件后文件过大的问题

文章目录 前言1. 创建新项目![请添加图片描述](https://img-blog.csdnimg.cn/36dcadc85d864a08b93af78b9e79ff6d.jpeg)2.删除原项目中的全部文件3.将要打包的文件放入该项目目录下4.创建虚拟环境5.设置解释器为虚拟环境中的python解释器6.查看是否成功使用虚拟环境中的python解…...

Ab3d.DXEngine 6.0 Crack 2023

Ab3d.DXEngine 不是另一个游戏引擎&#xff08;如Unity&#xff09;&#xff0c;它强迫您使用其游戏编辑器、其架构&#xff0c;并且需要许多技巧和窍门才能在标准 .Net 应用程序中使用。Ab3d.DXEngine 是一个新的渲染引擎&#xff0c;它是从头开始构建的&#xff0c;旨在用于标…...

Wireshark抓包常用指令

1.常用过滤规则 指定源地址&#xff1a; ip.src 10.0.1.123ip.src 10.0.1.123 && udphttp数据链路层&#xff1a;筛选mac地址为04:f9:38:ad:13:26的数据包----eth.src 04:f9:38:ad:13:26筛选源mac地址为04:f9:38:ad:13:26的数据包----eth.src 04:f9:38:ad:13:26网…...

Docker Swarm

Docker Swarm提供 Docker 容器集群服务&#xff0c;是 Docker 官方对容器云生态进行支持的核心方案。将多个 Docker 主机封装为单个大型的虚拟 Docker 主机&#xff0c;快速打造一套容器云平台。 Swarm mode内置 kv 存储功能&#xff0c;提供了众多的新特性&#xff0c;比如&a…...

jupyter notebook安装和删除kernel的解决方案

大家好,我是爱编程的喵喵。双985硕士毕业,现担任全栈工程师一职,热衷于将数据思维应用到工作与生活中。从事机器学习以及相关的前后端开发工作。曾在阿里云、科大讯飞、CCF等比赛获得多次Top名次。现为CSDN博客专家、人工智能领域优质创作者。喜欢通过博客创作的方式对所学的…...

中级深入--day16

爬虫(Spider)&#xff0c;反爬虫(Anti-Spider)&#xff0c;反反爬虫(Anti-Anti-Spider) 之间恢宏壮阔的斗争... Day 1 小黄想要某站上所有的电影&#xff0c;写了标准的爬虫(基于HttpClient库)&#xff0c;不断地遍历某站的电影列表页面&#xff0c;根据 Html 分析电影名字存进…...

生成xcframework

打包 XCFramework 的方法 XCFramework 是苹果推出的一种多平台二进制分发格式&#xff0c;可以包含多个架构和平台的代码。打包 XCFramework 通常用于分发库或框架。 使用 Xcode 命令行工具打包 通过 xcodebuild 命令可以打包 XCFramework。确保项目已经配置好需要支持的平台…...

多模态2025:技术路线“神仙打架”,视频生成冲上云霄

文&#xff5c;魏琳华 编&#xff5c;王一粟 一场大会&#xff0c;聚集了中国多模态大模型的“半壁江山”。 智源大会2025为期两天的论坛中&#xff0c;汇集了学界、创业公司和大厂等三方的热门选手&#xff0c;关于多模态的集中讨论达到了前所未有的热度。其中&#xff0c;…...

springboot 百货中心供应链管理系统小程序

一、前言 随着我国经济迅速发展&#xff0c;人们对手机的需求越来越大&#xff0c;各种手机软件也都在被广泛应用&#xff0c;但是对于手机进行数据信息管理&#xff0c;对于手机的各种软件也是备受用户的喜爱&#xff0c;百货中心供应链管理系统被用户普遍使用&#xff0c;为方…...

Java 语言特性(面试系列1)

一、面向对象编程 1. 封装&#xff08;Encapsulation&#xff09; 定义&#xff1a;将数据&#xff08;属性&#xff09;和操作数据的方法绑定在一起&#xff0c;通过访问控制符&#xff08;private、protected、public&#xff09;隐藏内部实现细节。示例&#xff1a; public …...

大型活动交通拥堵治理的视觉算法应用

大型活动下智慧交通的视觉分析应用 一、背景与挑战 大型活动&#xff08;如演唱会、马拉松赛事、高考中考等&#xff09;期间&#xff0c;城市交通面临瞬时人流车流激增、传统摄像头模糊、交通拥堵识别滞后等问题。以演唱会为例&#xff0c;暖城商圈曾因观众集中离场导致周边…...

条件运算符

C中的三目运算符&#xff08;也称条件运算符&#xff0c;英文&#xff1a;ternary operator&#xff09;是一种简洁的条件选择语句&#xff0c;语法如下&#xff1a; 条件表达式 ? 表达式1 : 表达式2• 如果“条件表达式”为true&#xff0c;则整个表达式的结果为“表达式1”…...

家政维修平台实战20:权限设计

目录 1 获取工人信息2 搭建工人入口3 权限判断总结 目前我们已经搭建好了基础的用户体系&#xff0c;主要是分成几个表&#xff0c;用户表我们是记录用户的基础信息&#xff0c;包括手机、昵称、头像。而工人和员工各有各的表。那么就有一个问题&#xff0c;不同的角色&#xf…...

Typeerror: cannot read properties of undefined (reading ‘XXX‘)

最近需要在离线机器上运行软件&#xff0c;所以得把软件用docker打包起来&#xff0c;大部分功能都没问题&#xff0c;出了一个奇怪的事情。同样的代码&#xff0c;在本机上用vscode可以运行起来&#xff0c;但是打包之后在docker里出现了问题。使用的是dialog组件&#xff0c;…...

HarmonyOS运动开发:如何用mpchart绘制运动配速图表

##鸿蒙核心技术##运动开发##Sensor Service Kit&#xff08;传感器服务&#xff09;# 前言 在运动类应用中&#xff0c;运动数据的可视化是提升用户体验的重要环节。通过直观的图表展示运动过程中的关键数据&#xff0c;如配速、距离、卡路里消耗等&#xff0c;用户可以更清晰…...

Java编程之桥接模式

定义 桥接模式&#xff08;Bridge Pattern&#xff09;属于结构型设计模式&#xff0c;它的核心意图是将抽象部分与实现部分分离&#xff0c;使它们可以独立地变化。这种模式通过组合关系来替代继承关系&#xff0c;从而降低了抽象和实现这两个可变维度之间的耦合度。 用例子…...