当前位置: 首页 > 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;还会删除配置文件、数据文件和日志…...

简易版抽奖活动的设计技术方案

1.前言 本技术方案旨在设计一套完整且可靠的抽奖活动逻辑,确保抽奖活动能够公平、公正、公开地进行,同时满足高并发访问、数据安全存储与高效处理等需求,为用户提供流畅的抽奖体验,助力业务顺利开展。本方案将涵盖抽奖活动的整体架构设计、核心流程逻辑、关键功能实现以及…...

在HarmonyOS ArkTS ArkUI-X 5.0及以上版本中,手势开发全攻略:

在 HarmonyOS 应用开发中&#xff0c;手势交互是连接用户与设备的核心纽带。ArkTS 框架提供了丰富的手势处理能力&#xff0c;既支持点击、长按、拖拽等基础单一手势的精细控制&#xff0c;也能通过多种绑定策略解决父子组件的手势竞争问题。本文将结合官方开发文档&#xff0c…...

Swift 协议扩展精进之路:解决 CoreData 托管实体子类的类型不匹配问题(下)

概述 在 Swift 开发语言中&#xff0c;各位秃头小码农们可以充分利用语法本身所带来的便利去劈荆斩棘。我们还可以恣意利用泛型、协议关联类型和协议扩展来进一步简化和优化我们复杂的代码需求。 不过&#xff0c;在涉及到多个子类派生于基类进行多态模拟的场景下&#xff0c;…...

深入浅出:JavaScript 中的 `window.crypto.getRandomValues()` 方法

深入浅出&#xff1a;JavaScript 中的 window.crypto.getRandomValues() 方法 在现代 Web 开发中&#xff0c;随机数的生成看似简单&#xff0c;却隐藏着许多玄机。无论是生成密码、加密密钥&#xff0c;还是创建安全令牌&#xff0c;随机数的质量直接关系到系统的安全性。Jav…...

在Ubuntu中设置开机自动运行(sudo)指令的指南

在Ubuntu系统中&#xff0c;有时需要在系统启动时自动执行某些命令&#xff0c;特别是需要 sudo权限的指令。为了实现这一功能&#xff0c;可以使用多种方法&#xff0c;包括编写Systemd服务、配置 rc.local文件或使用 cron任务计划。本文将详细介绍这些方法&#xff0c;并提供…...

CMake控制VS2022项目文件分组

我们可以通过 CMake 控制源文件的组织结构,使它们在 VS 解决方案资源管理器中以“组”(Filter)的形式进行分类展示。 🎯 目标 通过 CMake 脚本将 .cpp、.h 等源文件分组显示在 Visual Studio 2022 的解决方案资源管理器中。 ✅ 支持的方法汇总(共4种) 方法描述是否推荐…...

sipsak:SIP瑞士军刀!全参数详细教程!Kali Linux教程!

简介 sipsak 是一个面向会话初始协议 (SIP) 应用程序开发人员和管理员的小型命令行工具。它可以用于对 SIP 应用程序和设备进行一些简单的测试。 sipsak 是一款 SIP 压力和诊断实用程序。它通过 sip-uri 向服务器发送 SIP 请求&#xff0c;并检查收到的响应。它以以下模式之一…...

省略号和可变参数模板

本文主要介绍如何展开可变参数的参数包 1.C语言的va_list展开可变参数 #include <iostream> #include <cstdarg>void printNumbers(int count, ...) {// 声明va_list类型的变量va_list args;// 使用va_start将可变参数写入变量argsva_start(args, count);for (in…...

NPOI操作EXCEL文件 ——CAD C# 二次开发

缺点:dll.版本容易加载错误。CAD加载插件时&#xff0c;没有加载所有类库。插件运行过程中用到某个类库&#xff0c;会从CAD的安装目录找&#xff0c;找不到就报错了。 【方案2】让CAD在加载过程中把类库加载到内存 【方案3】是发现缺少了哪个库&#xff0c;就用插件程序加载进…...

SpringAI实战:ChatModel智能对话全解

一、引言&#xff1a;Spring AI 与 Chat Model 的核心价值 &#x1f680; 在 Java 生态中集成大模型能力&#xff0c;Spring AI 提供了高效的解决方案 &#x1f916;。其中 Chat Model 作为核心交互组件&#xff0c;通过标准化接口简化了与大语言模型&#xff08;LLM&#xff0…...