【搜索】DFS连通性模型
算法提高课笔记
目录
- 迷宫
- 题意
- 思路
- 代码
- 红与黑
- 题意
- 思路
- 代码
DFS 的搜索分为两大部分:
- 内部搜索:一个图中从一个点搜到另一个点
- 外部搜索:从一张图(状态)搜到另一张图(状态)
在第一个部分里是图内部点的搜索,每个点只能搜一次,因此搜过的点不需要恢复到原来的(还没被搜过的)状态(意思就是st数组不恢复)
而第二个部分是点的集合之间的搜索,每次搜索完一定要恢复到原有状态才可以进行下一步搜索(意思就是st数组每次需要恢复原状)
迷宫
原题链接
一天Extense在森林里探险的时候不小心走入了一个迷宫,迷宫可以看成是由 n∗n 的格点组成,每个格点只有2种状态,.和#,前者表示可以通行后者表示不能通行。
同时当Extense处在某个格点时,他只能移动到东南西北(或者说上下左右)四个方向之一的相邻格点上,Extense想要从点A走到点B,问在不走出迷宫的情况下能不能办到。
如果起点或者终点有一个不能通行(为#),则看成无法办到。
注意:A、B不一定是两个不同的点。
输入格式
第1行是测试数据的组数 k,后面跟着 k 组输入。
每组测试数据的第1行是一个正整数 n,表示迷宫的规模是 n∗n 的。
接下来是一个 n∗n 的矩阵,矩阵中的元素为.或者#。
再接下来一行是 4 个整数 ha,la,hb,lb,描述 A 处在第 ha 行, 第 la 列,B 处在第 hb 行, 第 lb 列。
注意到 ha,la,hb,lb 全部是从 0 开始计数的。
输出格式
k行,每行输出对应一个输入。
能办到则输出“YES”,否则输出“NO”。
数据范围
1 ≤ n ≤ 100
输入样例
2
3
.##
..#
#..
0 0 2 2
5
.....
###.#
..#..
###..
...#.
0 0 4 0
输出样例
YES
NO
题意
给出一张图两个点,问能不能从一个点走到另一个点
思路
直接bfs遍历看能不能从一个点遍历到另一个
代码
#include <bits/stdc++.h>using namespace std;const int N = 110;int n;
char g[N][N]; // 存图
int xa, ya, xb, yb; // 标记起点终点
int dx[4] = {0, 0, 1, -1}, dy[4] = {1, -1, 0, 0};
bool st[N][N]; // 判重bool dfs(int x, int y)
{if (g[x][y] == '#') return false;if (x == xb && y == yb) return true;st[x][y] = true;for (int i = 0; i < 4; i ++ ) // 遍历四个操作{int a = x + dx[i], b = y + dy[i];if (a < 0 || a >= n || b < 0 || b >= n) continue; // 位置不合法if (st[a][b]) continue; // 已遍历if (dfs(a, b)) return true;} return false;
}int main()
{ios::sync_with_stdio(false);cin.tie(0); cout.tie(0);int t;cin >> t;while (t -- ){cin >> n;for (int i = 0; i < n; i ++ ) cin >> g[i];cin >> xa >> ya >> xb >> yb;memset(st, false, sizeof st);if (dfs(xa, ya)) cout << "YES\n";else cout << "NO\n";}
}
红与黑
原题链接
有一间长方形的房子,地上铺了红色、黑色两种颜色的正方形瓷砖。
你站在其中一块黑色的瓷砖上,只能向相邻(上下左右四个方向)的黑色瓷砖移动。
请写一个程序,计算你总共能够到达多少块黑色的瓷砖。
输入格式
输入包括多个数据集合。
每个数据集合的第一行是两个整数 W 和 H,分别表示 x 方向和 y 方向瓷砖的数量。
在接下来的 H 行中,每行包括 W 个字符。每个字符表示一块瓷砖的颜色,规则如下
1)‘.’:黑色的瓷砖;
2)‘#’:红色的瓷砖;
3)‘@’:黑色的瓷砖,并且你站在这块瓷砖上。该字符在每个数据集合中唯一出现一次。
当在一行中读入的是两个零时,表示输入结束。
输出格式
对每个数据集合,分别输出一行,显示你从初始位置出发能到达的瓷砖数(记数时包括初始位置的瓷砖)。
数据范围
1 ≤ W , H ≤ 20
输入样例
6 9
....#.
.....#
......
......
......
......
......
#@...#
.#..#.
0 0
输出样例
45
题意
一个图分为红黑方块,问某一个黑方块的连通块个数
思路
本质上是个Flood Fill问题,可以用BFS实现
用DFS也是一样的,只是搜索顺序不一样
代码
#include <bits/stdc++.h>using namespace std;const int N = 25;int n, m;
char g[N][N]; // 存图
bool st[N][N]; // 判重
int dx[4] = {0, 0, -1, 1}, dy[4] = {1, -1, 0, 0};int dfs(int x, int y)
{int cnt = 1;st[x][y] = true;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) continue; // 位置不合法if (g[a][b] != '.') continue; // 不是黑色的if (st[a][b]) continue; // 已遍历cnt += dfs(a, b);}return cnt;
}int main()
{ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);while (cin >> m >> n, n || m){for (int i = 0; i < n; i ++ ) cin >> g[i];int x, y;for (int i = 0; i < n; i ++ ) for (int j = 0; j < m; j ++ )if (g[i][j] == '@') // 找起点{x = i;y = j;}memset(st, false, sizeof st);cout << dfs(x, y) << '\n';}
}
相关文章:
【搜索】DFS连通性模型
算法提高课笔记 目录 迷宫题意思路代码 红与黑题意思路代码 DFS 的搜索分为两大部分: 内部搜索:一个图中从一个点搜到另一个点外部搜索:从一张图(状态)搜到另一张图(状态) 在第一个部分里是图…...
项目优化后续 ,手撸一个精简版VUE项目框架!
之前说过项目之前用的vben框架,在优化完性能后打包效果由原来的纯代码96M变成了56M,后续来啦,通过更换框架,代码压缩到了36M撒花~ 现在就来详细说说是怎么手撸一个框架的! 方案: 搭建一套 vite vue3 a…...
【深度学习笔记】TensorFlow 基础
在 TensorFlow 2.0 及之后的版本中,默认采用 Eager Execution 的方式,不再使用 1.0 版本的 Session 创建会话。Eager Execution 使用更自然地方式组织代码,无需构建计算图,可以立即进行数学计算,简化了代码调试的过程。…...
面试题-springcloud中的负载均衡是如何实现的?
一句话导读 Springcloud中的负载均衡是通过Ribbon实现的,自带有很多负载均衡策略,如:包括轮询(Round Robin)、随机(Random)、加权轮询(Weighted Round Robin)、加权随机&…...
flink的ProcessWindowFunction函数的三种状态
背景 在处理窗口函数时,ProcessWindowFunction处理函数可以定义三个状态: 富函数getRuntimeContext.getState, 每个key每个窗口的状态context.windowState(),每个key的状态context.globalState,那么这几个状态之间有什么关系呢? …...
day50-springboot+ajax分页
分页依赖: <dependency> <groupId>com.github.pagehelper</groupId> <artifactId>pagehelper-spring-boot-starter</artifactId> <version>1.0.0</version> </dependency> 配置: …...
Win7 专业版Windows time w32time服务电脑重启后老是已停止
环境: Win7 专业版 问题描述: Win7 专业版Windows time w32time服务电脑重启后老是已停止 解决方案: 1.检查启动Remote Procedure Call (RPC)、Remote Procedure Call (RPC) Locator,DCOM Server Process Launcher这三个服务是…...
全网最强,接口自动化测试-token登录关联实战总结(超详细)
目录:导读 前言一、Python编程入门到精通二、接口自动化项目实战三、Web自动化项目实战四、App自动化项目实战五、一线大厂简历六、测试开发DevOps体系七、常用自动化测试工具八、JMeter性能测试九、总结(尾部小惊喜) 前言 在PC端登录公司的…...
OLAP ModelKit Crack,ADO.NET和IList
OLAP ModelKit Crack,ADO.NET和IList OLAP ModelKit是一个多功能的.NET OLAP组件,用C#编写,只包含100%托管代码。它具有XP主题的外观,并能够使用任何.NET数据源(ADO.NET和IList)。借助任何第三方组件(尤其是图表组件)呈现数据的能力扩展了产品…...
4 三组例子,用OpenCV玩转图像-AI-python
读取,缩放,旋转,写入图像 首先导入包,为了显示导入matplotlib/为了在matplotlib显示 导入CV2/查看版本 导入图片/查看图片类型 图片数组 数组大小 对于opencv通道顺序蓝色B、绿色G、红色R matplotlib通道顺序为 红色R、绿色G、蓝…...
计算机网络-三种交换方式
计算机网络-三种交换方式 电路交换(Circuit Switching) 电话交换机接通电话线的方式称为电路交换从通信资源分配的角度来看,交换(Switching)就是按照某种方式动态的分配传输线路的资源 电话交换机 为了解决电话之间通信两两之间连线过多,所以产生了电话…...
03 制作Ubuntu启动盘
1 软碟通 我是用软碟通制作启动盘。安装软碟通时一定要把虚拟光驱给勾选上,其余两个可以看你心情。 2 镜像文件 我使用清华镜像网站找到的Ubuntu镜像文件。 Index of /ubuntu-releases/ | 清华大学开源软件镜像站 | Tsinghua Open Source Mirror 请自己选择镜像…...
【JavaSE】String类中常用的字符串方法(超全)
目录 1.求字符串的长度 2.判断字符串是否为空 3.String对象的比较 3.1 判断字符串是否相同 3.2 比较字符串大小 3.3 忽略大小写比较 4.字符串查找 5.转化 5.1 数值和字符串转化 5.1.1 数字转字符串 valueof 5.1.2 valueOf的其他用法 5.1.3 字符串转数字 5.2 大小写转…...
Bootload U-Boot分析
Bootloader是在操作系统运行之前执行的一段小程序。通过这段小程序可以初始化硬件设备、建立内存空间的映射表,从而建立适当的系统软硬件环境,为最终调用操作系统内核做好准备。 对于嵌入式系统,Bootloader是基于特定硬件平台来实现的。因此…...
以公益之行,筑责任之心——2023年中创算力爱心公益助学活动
捐资助学是一项功在当代、利在千秋的义举。 高考录取工作已经开始,一张张高校录取通知书也陆续送达各位准大学生手中。当他们怀揣着对大学的好奇与憧憬,准备迈进理想的大学时,还有一群人,他们渴望知识,却因经济困难而…...
【机器学习】处理样本不平衡的问题
文章目录 样本不均衡的概念及影响样本不均衡的解决方法样本层面欠采样 (undersampling)过采样数据增强 损失函数层面模型层面采样集成学习 决策及评估指标 样本不均衡的概念及影响 机器学习中,样本不均衡问题经常遇到,比如在金融…...
Android前沿技术?Jetpack如何?
Jetpack Compose是Android开发领域的一项前沿技术,它提供了一种全新的方式来构建用户界面。近年来,Jetpack Compose在各大招聘等网站上的招聘岗位逐渐增多,薪资待遇也相应提高。本文将从招聘岗位的薪资与技术要求入手,分析Jetpack…...
为react项目添加开发/提交规范(前端工程化、eslint、prettier、husky、commitlint、stylelint)
因历史遗留原因,接手的项目没有代码提醒/格式化,包括 eslint、pretttier,也没有 commit 提交校验,如 husky、commitlint、stylelint,与其期待自己或者同事的代码写得完美无缺,不如通过一些工具来进行规范和…...
小研究 - MySQL 数据库安全加固技术的研究(一)
随着信息系统的日益普及,后台数据库的安全问题逐步被人们重视起来。以当下热门的MySQL 数据库为例,通过分析数据库的安全机制以及总结数据库面临的安全风险,针对性地提出了相应的加固策略,为数据库的安全加固工作提供了技术支撑。…...
linux安装redis带图详细
如何在Linux系统中卸载Redis 一、使用apt-get卸载Redis sudo apt-get purge redis-server如果使用apt-get安装Redis,可以使用apt-get purge命令完全卸载Redis。其中,purge命令会不仅仅删除Redis二进制文件,还会删除配置文件、数据文件和日志…...
通过Wrangler CLI在worker中创建数据库和表
官方使用文档:Getting started Cloudflare D1 docs 创建数据库 在命令行中执行完成之后,会在本地和远程创建数据库: npx wranglerlatest d1 create prod-d1-tutorial 在cf中就可以看到数据库: 现在,您的Cloudfla…...
【Redis技术进阶之路】「原理分析系列开篇」分析客户端和服务端网络诵信交互实现(服务端执行命令请求的过程 - 初始化服务器)
服务端执行命令请求的过程 【专栏简介】【技术大纲】【专栏目标】【目标人群】1. Redis爱好者与社区成员2. 后端开发和系统架构师3. 计算机专业的本科生及研究生 初始化服务器1. 初始化服务器状态结构初始化RedisServer变量 2. 加载相关系统配置和用户配置参数定制化配置参数案…...
基于当前项目通过npm包形式暴露公共组件
1.package.sjon文件配置 其中xh-flowable就是暴露出去的npm包名 2.创建tpyes文件夹,并新增内容 3.创建package文件夹...
【SQL学习笔记1】增删改查+多表连接全解析(内附SQL免费在线练习工具)
可以使用Sqliteviz这个网站免费编写sql语句,它能够让用户直接在浏览器内练习SQL的语法,不需要安装任何软件。 链接如下: sqliteviz 注意: 在转写SQL语法时,关键字之间有一个特定的顺序,这个顺序会影响到…...
CMake控制VS2022项目文件分组
我们可以通过 CMake 控制源文件的组织结构,使它们在 VS 解决方案资源管理器中以“组”(Filter)的形式进行分类展示。 🎯 目标 通过 CMake 脚本将 .cpp、.h 等源文件分组显示在 Visual Studio 2022 的解决方案资源管理器中。 ✅ 支持的方法汇总(共4种) 方法描述是否推荐…...
STM32HAL库USART源代码解析及应用
STM32HAL库USART源代码解析 前言STM32CubeIDE配置串口USART和UART的选择使用模式参数设置GPIO配置DMA配置中断配置硬件流控制使能生成代码解析和使用方法串口初始化__UART_HandleTypeDef结构体浅析HAL库代码实际使用方法使用轮询方式发送使用轮询方式接收使用中断方式发送使用中…...
Linux nano命令的基本使用
参考资料 GNU nanoを使いこなすnano基础 目录 一. 简介二. 文件打开2.1 普通方式打开文件2.2 只读方式打开文件 三. 文件查看3.1 打开文件时,显示行号3.2 翻页查看 四. 文件编辑4.1 Ctrl K 复制 和 Ctrl U 粘贴4.2 Alt/Esc U 撤回 五. 文件保存与退出5.1 Ctrl …...
[大语言模型]在个人电脑上部署ollama 并进行管理,最后配置AI程序开发助手.
ollama官网: 下载 https://ollama.com/ 安装 查看可以使用的模型 https://ollama.com/search 例如 https://ollama.com/library/deepseek-r1/tags # deepseek-r1:7bollama pull deepseek-r1:7b改token数量为409622 16384 ollama命令说明 ollama serve #:…...
Git常用命令完全指南:从入门到精通
Git常用命令完全指南:从入门到精通 一、基础配置命令 1. 用户信息配置 # 设置全局用户名 git config --global user.name "你的名字"# 设置全局邮箱 git config --global user.email "你的邮箱example.com"# 查看所有配置 git config --list…...
windows系统MySQL安装文档
概览:本文讨论了MySQL的安装、使用过程中涉及的解压、配置、初始化、注册服务、启动、修改密码、登录、退出以及卸载等相关内容,为学习者提供全面的操作指导。关键要点包括: 解压 :下载完成后解压压缩包,得到MySQL 8.…...
