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

【搜索】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 的搜索分为两大部分&#xff1a; 内部搜索&#xff1a;一个图中从一个点搜到另一个点外部搜索&#xff1a;从一张图&#xff08;状态&#xff09;搜到另一张图&#xff08;状态&#xff09; 在第一个部分里是图…...

项目优化后续 ,手撸一个精简版VUE项目框架!

之前说过项目之前用的vben框架&#xff0c;在优化完性能后打包效果由原来的纯代码96M变成了56M&#xff0c;后续来啦&#xff0c;通过更换框架&#xff0c;代码压缩到了36M撒花~ 现在就来详细说说是怎么手撸一个框架的&#xff01; 方案&#xff1a; 搭建一套 vite vue3 a…...

【深度学习笔记】TensorFlow 基础

在 TensorFlow 2.0 及之后的版本中&#xff0c;默认采用 Eager Execution 的方式&#xff0c;不再使用 1.0 版本的 Session 创建会话。Eager Execution 使用更自然地方式组织代码&#xff0c;无需构建计算图&#xff0c;可以立即进行数学计算&#xff0c;简化了代码调试的过程。…...

面试题-springcloud中的负载均衡是如何实现的?

一句话导读 Springcloud中的负载均衡是通过Ribbon实现的&#xff0c;自带有很多负载均衡策略&#xff0c;如&#xff1a;包括轮询&#xff08;Round Robin&#xff09;、随机&#xff08;Random&#xff09;、加权轮询&#xff08;Weighted Round Robin&#xff09;、加权随机&…...

flink的ProcessWindowFunction函数的三种状态

背景 在处理窗口函数时&#xff0c;ProcessWindowFunction处理函数可以定义三个状态&#xff1a; 富函数getRuntimeContext.getState, 每个key每个窗口的状态context.windowState(),每个key的状态context.globalState&#xff0c;那么这几个状态之间有什么关系呢&#xff1f; …...

day50-springboot+ajax分页

分页依赖&#xff1a; <dependency> <groupId>com.github.pagehelper</groupId> <artifactId>pagehelper-spring-boot-starter</artifactId> <version>1.0.0</version> </dependency> 配置&#xff1a; …...

Win7 专业版Windows time w32time服务电脑重启后老是已停止

环境&#xff1a; Win7 专业版 问题描述&#xff1a; Win7 专业版Windows time w32time服务电脑重启后老是已停止 解决方案&#xff1a; 1.检查启动Remote Procedure Call (RPC)、Remote Procedure Call (RPC) Locator&#xff0c;DCOM Server Process Launcher这三个服务是…...

全网最强,接口自动化测试-token登录关联实战总结(超详细)

目录&#xff1a;导读 前言一、Python编程入门到精通二、接口自动化项目实战三、Web自动化项目实战四、App自动化项目实战五、一线大厂简历六、测试开发DevOps体系七、常用自动化测试工具八、JMeter性能测试九、总结&#xff08;尾部小惊喜&#xff09; 前言 在PC端登录公司的…...

OLAP ModelKit Crack,ADO.NET和IList

OLAP ModelKit Crack,ADO.NET和IList OLAP ModelKit是一个多功能的.NET OLAP组件&#xff0c;用C#编写&#xff0c;只包含100%托管代码。它具有XP主题的外观&#xff0c;并能够使用任何.NET数据源(ADO.NET和IList)。借助任何第三方组件(尤其是图表组件)呈现数据的能力扩展了产品…...

4 三组例子,用OpenCV玩转图像-AI-python

读取&#xff0c;缩放&#xff0c;旋转&#xff0c;写入图像 首先导入包&#xff0c;为了显示导入matplotlib/为了在matplotlib显示 导入CV2/查看版本 导入图片/查看图片类型 图片数组 数组大小 对于opencv通道顺序蓝色B、绿色G、红色R matplotlib通道顺序为 红色R、绿色G、蓝…...

计算机网络-三种交换方式

计算机网络-三种交换方式 电路交换(Circuit Switching) 电话交换机接通电话线的方式称为电路交换从通信资源分配的角度来看&#xff0c;交换(Switching)就是按照某种方式动态的分配传输线路的资源 电话交换机 为了解决电话之间通信两两之间连线过多&#xff0c;所以产生了电话…...

03 制作Ubuntu启动盘

1 软碟通 我是用软碟通制作启动盘。安装软碟通时一定要把虚拟光驱给勾选上&#xff0c;其余两个可以看你心情。 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是在操作系统运行之前执行的一段小程序。通过这段小程序可以初始化硬件设备、建立内存空间的映射表&#xff0c;从而建立适当的系统软硬件环境&#xff0c;为最终调用操作系统内核做好准备。 对于嵌入式系统&#xff0c;Bootloader是基于特定硬件平台来实现的。因此…...

以公益之行,筑责任之心——2023年中创算力爱心公益助学活动

捐资助学是一项功在当代、利在千秋的义举。 高考录取工作已经开始&#xff0c;一张张高校录取通知书也陆续送达各位准大学生手中。当他们怀揣着对大学的好奇与憧憬&#xff0c;准备迈进理想的大学时&#xff0c;还有一群人&#xff0c;他们渴望知识&#xff0c;却因经济困难而…...

【机器学习】处理样本不平衡的问题

文章目录 样本不均衡的概念及影响样本不均衡的解决方法样本层面欠采样 &#xff08;undersampling&#xff09;过采样数据增强 损失函数层面模型层面采样集成学习 决策及评估指标 样本不均衡的概念及影响 机器学习中&#xff0c;样本不均衡问题经常遇到&#xff0c;比如在金融…...

Android前沿技术?Jetpack如何?

Jetpack Compose是Android开发领域的一项前沿技术&#xff0c;它提供了一种全新的方式来构建用户界面。近年来&#xff0c;Jetpack Compose在各大招聘等网站上的招聘岗位逐渐增多&#xff0c;薪资待遇也相应提高。本文将从招聘岗位的薪资与技术要求入手&#xff0c;分析Jetpack…...

为react项目添加开发/提交规范(前端工程化、eslint、prettier、husky、commitlint、stylelint)

因历史遗留原因&#xff0c;接手的项目没有代码提醒/格式化&#xff0c;包括 eslint、pretttier&#xff0c;也没有 commit 提交校验&#xff0c;如 husky、commitlint、stylelint&#xff0c;与其期待自己或者同事的代码写得完美无缺&#xff0c;不如通过一些工具来进行规范和…...

小研究 - MySQL 数据库安全加固技术的研究(一)

随着信息系统的日益普及&#xff0c;后台数据库的安全问题逐步被人们重视起来。以当下热门的MySQL 数据库为例&#xff0c;通过分析数据库的安全机制以及总结数据库面临的安全风险&#xff0c;针对性地提出了相应的加固策略&#xff0c;为数据库的安全加固工作提供了技术支撑。…...

linux安装redis带图详细

如何在Linux系统中卸载Redis 一、使用apt-get卸载Redis sudo apt-get purge redis-server如果使用apt-get安装Redis&#xff0c;可以使用apt-get purge命令完全卸载Redis。其中&#xff0c;purge命令会不仅仅删除Redis二进制文件&#xff0c;还会删除配置文件、数据文件和日志…...

Neo4j 集群管理:原理、技术与最佳实践深度解析

Neo4j 的集群技术是其企业级高可用性、可扩展性和容错能力的核心。通过深入分析官方文档,本文将系统阐述其集群管理的核心原理、关键技术、实用技巧和行业最佳实践。 Neo4j 的 Causal Clustering 架构提供了一个强大而灵活的基石,用于构建高可用、可扩展且一致的图数据库服务…...

WEB3全栈开发——面试专业技能点P2智能合约开发(Solidity)

一、Solidity合约开发 下面是 Solidity 合约开发 的概念、代码示例及讲解&#xff0c;适合用作学习或写简历项目背景说明。 &#x1f9e0; 一、概念简介&#xff1a;Solidity 合约开发 Solidity 是一种专门为 以太坊&#xff08;Ethereum&#xff09;平台编写智能合约的高级编…...

全志A40i android7.1 调试信息打印串口由uart0改为uart3

一&#xff0c;概述 1. 目的 将调试信息打印串口由uart0改为uart3。 2. 版本信息 Uboot版本&#xff1a;2014.07&#xff1b; Kernel版本&#xff1a;Linux-3.10&#xff1b; 二&#xff0c;Uboot 1. sys_config.fex改动 使能uart3(TX:PH00 RX:PH01)&#xff0c;并让boo…...

【Oracle】分区表

个人主页&#xff1a;Guiat 归属专栏&#xff1a;Oracle 文章目录 1. 分区表基础概述1.1 分区表的概念与优势1.2 分区类型概览1.3 分区表的工作原理 2. 范围分区 (RANGE Partitioning)2.1 基础范围分区2.1.1 按日期范围分区2.1.2 按数值范围分区 2.2 间隔分区 (INTERVAL Partit…...

有限自动机到正规文法转换器v1.0

1 项目简介 这是一个功能强大的有限自动机&#xff08;Finite Automaton, FA&#xff09;到正规文法&#xff08;Regular Grammar&#xff09;转换器&#xff0c;它配备了一个直观且完整的图形用户界面&#xff0c;使用户能够轻松地进行操作和观察。该程序基于编译原理中的经典…...

【JavaSE】多线程基础学习笔记

多线程基础 -线程相关概念 程序&#xff08;Program&#xff09; 是为完成特定任务、用某种语言编写的一组指令的集合简单的说:就是我们写的代码 进程 进程是指运行中的程序&#xff0c;比如我们使用QQ&#xff0c;就启动了一个进程&#xff0c;操作系统就会为该进程分配内存…...

elementUI点击浏览table所选行数据查看文档

项目场景&#xff1a; table按照要求特定的数据变成按钮可以点击 解决方案&#xff1a; <el-table-columnprop"mlname"label"名称"align"center"width"180"><template slot-scope"scope"><el-buttonv-if&qu…...

c# 局部函数 定义、功能与示例

C# 局部函数&#xff1a;定义、功能与示例 1. 定义与功能 局部函数&#xff08;Local Function&#xff09;是嵌套在另一个方法内部的私有方法&#xff0c;仅在包含它的方法内可见。 • 作用&#xff1a;封装仅用于当前方法的逻辑&#xff0c;避免污染类作用域&#xff0c;提升…...

QT开发技术【ffmpeg + QAudioOutput】音乐播放器

一、 介绍 使用ffmpeg 4.2.2 在数字化浪潮席卷全球的当下&#xff0c;音视频内容犹如璀璨繁星&#xff0c;点亮了人们的生活与工作。从短视频平台上令人捧腹的搞笑视频&#xff0c;到在线课堂中知识渊博的专家授课&#xff0c;再到影视平台上扣人心弦的高清大片&#xff0c;音…...

加密通信 + 行为分析:运营商行业安全防御体系重构

在数字经济蓬勃发展的时代&#xff0c;运营商作为信息通信网络的核心枢纽&#xff0c;承载着海量用户数据与关键业务传输&#xff0c;其安全防御体系的可靠性直接关乎国家安全、社会稳定与企业发展。随着网络攻击手段的不断升级&#xff0c;传统安全防护体系逐渐暴露出局限性&a…...