1113. 红与黑--Flood Fill 算法
目录
1113. 红与黑--Flood Fill 算法---宽搜(BFS)或DFS)
输入格式
输出格式
数据范围
输入样例:
输出样例:
思路:
1.BFS 思路:
2.DFS 思路
方法一:(BFS)代码:
方法二:深搜(DFS)代码:
运行结果:
1113. 红与黑--Flood Fill 算法---宽搜(BFS)或DFS)
有一间长方形的房子,地上铺了红色、黑色两种颜色的正方形瓷砖。
你站在其中一块黑色的瓷砖上,只能向相邻(上下左右四个方向)的黑色瓷砖移动。
请写一个程序,计算你总共能够到达多少块黑色的瓷砖。
输入格式
输入包括多个数据集合。
每个数据集合的第一行是两个整数 W 和 H,分别表示 x 方向和 y 方向瓷砖的数量。
在接下来的 HH 行中,每行包括 W 个字符。每个字符表示一块瓷砖的颜色,规则如下
1)‘.’:黑色的瓷砖;
2)‘#’:红色的瓷砖;
3)‘@’:黑色的瓷砖,并且你站在这块瓷砖上。该字符在每个数据集合中唯一出现一次。
当在一行中读入的是两个零时,表示输入结束。
输出格式
对每个数据集合,分别输出一行,显示你从初始位置出发能到达的瓷砖数(记数时包括初始位置的瓷砖)。
数据范围
1≤W,H≤20
输入样例:
6 9
....#.
.....#
......
......
......
......
......
#@...#
.#..#.
0 0
输出样例:
45
难度:简单 |
时/空限制:1s / 64MB |
总通过数:31526 |
总尝试数:54082 |
来源: 《信息学奥赛一本通》 |
算法标签 DFSFlood Fill |
思路:
1.BFS 思路:
偏移量:
2.DFS 思路
方法一:(BFS)代码:
#include <bits/stdc++.h>// 定义宏,便于快速访问 pair 类型中的元素
#define x first
#define y second// 引入标准命名空间
using namespace std;// 定义 pair 类型别名 PII,表示一对整数
typedef pair<int, int> PII;// 定义常量 N,表示矩阵的最大尺寸
const int N = 25;// 定义全局变量 g(存储矩阵)、n(矩阵行数)、m(矩阵列数)
char g[N][N];
int n, m; // 矩阵行与列// 定义偏移量数组 dx 和 dy,用于计算相邻格子的坐标
int dx[4] = {-1, 0, 1, 0}; // 每个方向x方向的偏移量:上、右、下、左
int dy[4] = {0, 1, 0, -1}; // 每个方向y方向的偏移量:上、右、下、左// 广度优先搜索(BFS)函数,参数:起始位置的行坐标 sx 和列坐标 sy
// 返回值:从起始位置开始,能够搜索到的点(值为 '.') 的数量
int bfs(int sx, int sy) {queue<PII> q; // 定义队列 q,用于存储待访问的格子坐标q.push({sx, sy}); // 将起始位置加入队列g[sx][sy] = '#'; // 将起始位置标记为 '#'int res = 0; // 初始化搜索到的点的数量为 0// 当队列不为空时,持续进行广度优先搜索while (!q.empty()) {auto t = q.front(); // 取队首元素(当前待访问的格子坐标)q.pop(); // 出队,移除已访问的格子坐标res++; // 计数器加一,表示找到一个可搜索的点// 遍历当前格子的四个相邻格子for (int i = 0; i < 4; i++) {int x = t.x + dx[i], y = t.y + dy[i]; // 计算相邻格子的坐标// 检查相邻格子是否在矩阵范围内、是否为 '.',若不符合条件则跳过if (x < 0 || x >= n || y < 0 || y >= m || g[x][y] != '.') continue;g[x][y] = '#'; // 将相邻格子标记为 '#',表示已访问q.push({x, y}); // 将相邻格子坐标加入队列,等待后续访问}}return res; // 返回搜索到的点的数量
}int main() {// 循环读取多组测试数据,直到输入为 0 0while (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;}// 调用 BFS 函数,计算并输出能够搜索到的点的数量cout << bfs(x, y) << endl;}return 0; // 主函数返回 0,表示程序正常结束
}
方法二:深搜(DFS)代码:
#include <bits/stdc++.h>using namespace std;// 定义全局变量 n(矩阵行数)、m(矩阵列数),以及矩阵 g
int n, m;
const int N = 25;
char g[N][N];// 定义偏移量数组 dx 和 dy,用于计算相邻格子的坐标
int dx[4] = {-1, 0, 1, 0}; // 水平方向的偏移量:左、中心、右、中心
int dy[4] = {0, 1, 0, -1}; // 垂直方向的偏移量:上、中心、下、中心// 深度优先搜索(DFS)函数,参数:当前格子的行坐标 x 和列坐标 y
// 返回值:以当前格子为根的连通区域中值为 '.' 的点的数量
int dfs(int x, int y) {int res = 1; // 初始化结果为 1,表示当前格子本身是一个可搜索的点g[x][y] = '#'; // 将当前格子标记为 '#',表示已访问// 遍历当前格子的四个相邻格子for (int i = 0; i < 4; i++) {int a = x + dx[i]; // 计算相邻格子的行坐标int b = y + dy[i]; // 计算相邻格子的列坐标// 检查相邻格子是否在矩阵范围内、是否为 '.',若符合条件则递归搜索if (a >= 0 && a < n && b >= 0 && b < m && g[a][b] == '.')res += dfs(a, b); // 将相邻格子的搜索结果累加到 res}return res; // 返回以当前格子为根的连通区域中值为 '.' 的点的数量
}int main() {// 循环读取多组测试数据,直到输入为 0 0while (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;}// 调用 DFS 函数,计算并输出以起始位置为根的连通区域中值为 '.' 的点的数量cout << dfs(x, y) << endl;}return 0; // 主函数返回 0,表示程序正常结束
}
实现了一个简单的深度优先搜索(DFS)算法,用于在一个给定的矩阵中,从标记为
'@'
的起始位置开始,搜索并标记所有相邻且值为'.'
的点。最终输出以起始位置为根的连通区域中值为'.'
的点的数量。
运行结果:
相关文章:
1113. 红与黑--Flood Fill 算法
目录 1113. 红与黑--Flood Fill 算法---宽搜(BFS)或DFS) 输入格式 输出格式 数据范围 输入样例: 输出样例: 思路: 1.BFS 思路: 2.DFS 思路 方法一:(BFS&#x…...
深入Java中间件:编程设计精粹
个人主页: 进朱者赤 阿里非典型程序员一枚 ,记录平平无奇程序员在大厂的打怪升级之路。 一起学习Java、大数据、数据结构算法(公众号同名) 引言 在Java中间件和框架里蕴藏着数不尽的编程设计精粹。这些设计不仅值得我们在日常编码…...
AUTOCAD输出或打印PDF文件时,如何将图形居中且布满图纸?
AUTOCAD输出或打印PDF文件时,如何将图形居中且布满图纸? 如下图所示,我们打开一份DWG格式的图纸文件,然后点击上方的“打印“图标, 如下图所示, 打印机/绘图仪这里选择“DWG To PDF“; 图纸尺寸:这里以普通的A4纸为例进行说明; 打印比例选择“布满图纸“; 打印偏移…...
unity socket udp 连接
使用此方法有助于udp在局域网内稳定的连接运行,已经过验证,为了保持彻底的稳定,可以考虑加入ping-pang进行网络处理,如果为了安全,请使用加密TCP 如果您要在大规,大项目的游戏中使用网络技术,建…...
【ensp】VLAN间通信的解决办法
目录 VLAN间通信简介 VLAN间通信的两种方式 借助三层设备路由器进行VLAN间的通信(也就是单臂路由) 在端口上创建子接口之后为什么需要开启arp广播,是因为他是子接口吗? 拓扑图 交换机配置 路由器配置 查看路由器配置 测试能否实现…...
接口测试框架搭建D22
整体架构和分层设计 run.py 运行测试用例,生成测试报告 test_cases/ 登录用例 注册用例 其他业务用例... data/ 测试数据 libs 第三方插件,比如HTMLTestRunnerNew config config.yaml 静态配置数据 config.py 动态配置数据 reports 测试报告…...
CASA模型教程
原文链接:CASA模型教程https://mp.weixin.qq.com/s?__bizMzUzNTczMDMxMg&mid2247600635&idx6&sna655a8de570edcaa435d6e917b66d9b3&chksmfa82081ccdf5810a33a778e8771bb116bde9e5a1f795daa4894e5b74de17b03ebe86d7cdcfe3&token1464653739&…...
算法思路-遥感语义分割与变化检测
遥感影像存在的问题 1.不同季节影像的差异 2. 影像云雾遮挡 3.影像由于传感器、地物反射、地物高度差等导致的畸变 抛开数据,目前语义分割任务面临的问题 1. 单一任务模型很难具有通用性 结合自然语言的大模型是否会是一个新的启发点 首先需要考虑根据影像我…...
动态规划专练( 231.打家劫舍Ⅱ)
231.打家劫舍Ⅱ 你是一个专业的小偷,计划偷窃沿街的房屋,每间房内都藏有一定的现金。这个地方所有的房屋都 围成一圈 ,这意味着第一个房屋和最后一个房屋是紧挨着的。同时,相邻的房屋装有相互连通的防盗系统,如果两间…...
K-means和逻辑回归
逻辑回归 一个事件的几率是该事件发生的概率/该事件不发生的概率:P/(1-P) 对数几率是:log(P/(1-P)) **考虑对输入x分类的模型:**log(P/(1-P))wx 则 Pexp(wx)/(exp(w*x)…...
3.2 iHRM人力资源 - 组织架构 - 编辑及删除
iHRM人力资源 - 组织架构 文章目录 iHRM人力资源 - 组织架构一、编辑功能1.1 表单弹层并数据回显1.2 编辑校验1.3 编辑 二、删除功能 一、编辑功能 编辑功能和新增功能用的组件其实是一个,结构几乎是一样的,其实是复用了组件,我们也省去了很…...
支付系统核心逻辑 — — 状态机(JavaGolang版本)
支付系统核心逻辑 — — 状态机 代码地址:https://github.com/ziyifast/ziyifast-code_instruction/tree/main/state_machine_demo 1 概念:FSM(有限状态机),模式之间转换 状态机,也叫有限状态机(…...
rest_framework_mongoengine实现后端的增删改查
rest_framework_mongoengine实现后端增删改查 一、增删改查 1. 继承ModelViewSet实现增删改查 父urls.py path("api/testapp/", include("apps.testapp.urls")), # 测试子urls.py # -*- coding: utf-8 -*- from django.urls import path from res…...
【精读文献】Scientific data|2017-2021年中国10米玉米农田变化制图
论文名称:Mapping annual 10-m maize cropland changes in China during 2017–2021 第一作者及通讯作者:Xingang Li, Ying Qu 第一作者单位及通讯作者单位:北京师范大学地理学部 文章发表期刊:《Scientific data》(…...
高光谱图像修复笔记
目录 RetinexFormer 也有MST-plus-plus代码,分辨率可以调 MST-plus-plus github地址: WACV2023 DSTrans RetinexFormer GitHub - caiyuanhao1998/Retinexformer: "Retinexformer: One-stage Retinex-based Transformer for Low-light Image E…...
GPS定位原理及应用分析
一.定位原理 1.卫星定位(GPS,北斗导航) ①.硬件构成(24颗卫星,可构建一套导航系统) 为何是24颗卫星? 可以做到全球覆盖,同一地点地球上空可观测到4颗卫星。 …...
Java面试篇9——并发编程
并发编程知识梳理 提示,此仅为面试,若想对线程有跟完整了解,请点击这里 提示:直接翻到最后面看面试真题,上面的为详解 面试考点 文档说明 在文档中对所有的面试题都进行了难易程度和出现频率的等级说明 星数越多代表…...
[RK3399 Linux] 使用busybox 1.36.1制作rootfs
一、 编译、安装、配置 busybox 1.1 下载源码 根文件系统是根据busybox来制作的。 下载地址:https://busybox.net/downloads/。 这里就以1.36.1版本为例进行编译安装介绍: 注意:编译linux内核与文件系统中的所有程序要使用相同的交叉编译器。 下载完成后解压: mkdir …...
JavaScript入门--循环
JavaScript入门--循环 一、for循环二、for in语句三、break语句四、continue语句五、while循环六、do-while语句一、for循环 先来看一个循环案例: for (i = 0; i < 5; i++) {...
【Delphi 爬虫库 1】GET和POST方法
文章目录 1.最简单的Get方法实现2.可自定义请求头、自定义Cookie的Get方法实现3.提取响应协议头4.Post方法实现单词翻译 爬虫的基本原理是根据需求获取信息并返回。就像当我们感到饥饿时,可以选择自己烹饪食物、外出就餐,或者订外卖一样。在编程中&#…...
[leetcode] 快乐数 E
:::details 编写一个算法来判断一个数 n 是不是快乐数。 「快乐数」 定义为: 对于一个正整数,每一次将该数替换为它每个位置上的数字的平方和。 然后重复这个过程直到这个数变为 1,也可能是 无限循环 但始终变不到 1。 如果这个过程 结果为 1…...
Lobe UI - 基于 AntDesign 开发的 AIGC Web 应用的开源 UI 组件库
今天推荐一个可以快速开发 ChatGPT UI 界面的组件库,质量很高,拿来就能用。 Lobe UI 是由 lobehub 团队开发的一套 web UI 组件库,和我之前推荐的很多通用型的 UI 组件库不同,Lobe UI 是专门为目前火热的 AIGC 应用开发而打造&am…...
Java常用类 -- Random类
该类实例用于生成伪随机数的流 伪随机数:通过算法算出来的数,是假的随机数 (一)具体使用 public static void main(String[] args) { Random r new Random(); System.out.println("随机出int类型的数据" r.nextIn…...
Docker安装Kong网关
文章目录 一、kong是什么?二、搭建步骤1.搭建PostgreSQL2.搭建Kong网关2.1、制作镜像2.2、数据库初始化2.3、启动Kong网关一、kong是什么? Github地址:https://github.com/Kong/kong Kong是一个可扩展、开源的云原生API网关,可以在分布式环境中管理、监控和安全地发布API…...
spispispi
SPI C.. & C.. logic是SPI的控制逻辑,芯片内部进行地址锁存、数据读写等操作,都是由控制逻辑自动完成。控制逻辑的左边是SPI的通信引脚,这些引脚和主控芯片相连,主控芯片通过SPI协议,把指令和数据发送给控制逻辑&a…...
MySQL——创建和插入
一、插入数据 INSERT 使用建议; 在任何情况下建议列出列名,在 VALUES 中插入值时,注意值和列的意义对应关系 values 指定的值顺序非常重要,决定了值是否被保存到正确的列中 在指定了列名的情况下,你可以仅对需要插入的列给到…...
【BUG】element-ui表格中使用video标签,数据翻页,video中的视频仍然显示第一页的视频,没有重新加载
BUG描述 遇到一个问题,使用element-ui构建的管理端后台,表格里面每一行都有一个video标签,里面有视频,当我翻页了以后,视频不会重新加载,仍然显示的是第一页的视频,代码如下: <e…...
【JavaSE】你真的了解内部类吗?
前言 本篇会详细讲解内部类的四种形式,让你掌握内部类~ 欢迎关注个人主页:逸狼 创造不易,可以点点赞吗~ 如有错误,欢迎指出~ 目录 前言 内部类介绍 实例内部类 定义 调用 静态内部类 定义 调用 匿名内部类 定义和调用1 调用方法2 …...
Vue3(二):报错调试,vue3响应式原理、computed和watch,ref,props,接口
一、准备工作调试 跟着张天禹老师看前几集的时候可能会遇到如下问题: 1.下载插件:Vue Language Features (Volar)或者直接下载vue-offical 2.npm run serve时运行时出现错误:Error: vitejs/plugin-vue requires vue (>3.2.13) …...
前端console用法分享
console对于前端人员来讲肯定都不陌生,相信大部分开发者都会使用console来进行调试,但它能做的绝不仅限于调试。 最常见的控制台方法 作为开发者,最常用的 console 方法如下: 控制台打印结果: 今天我分享的是一些 co…...
做网站想要个计算器功能/搜狗网址大全
iOS 7后,实际上APP拥有四种后台模式,无论是哪一种后台机制,均需要利用苹果给予的相应后台接口实现。新系统中,开发者可以灵活利用多种后台接口(API)实现更加智能的应用操作。 iOS 后台模式 无后台仅推送墓碑式智能调度后台真后台无…...
马云为什么做网站/文明seo
Enumable类型是linq to object 是一个很特殊的类型 这个类型的数据源都是在程序的内存中 Queryable类型是 Linq to sql 对数据库进行操作都是这个类型 这个类型会生成表达式目录树 方法体只能有一行代码 Expression 表达式目录树 ///外链接 需要用join into …...
wordpress主题设置导出/大一网页设计作业成品
这题比较简单,主要是list.sort的运用,策略:先将导弹的射程高度从大到小排序,之前需要记录导弹发射时时间上的相对位置。然后对排好序的list遍历,每次找到所有比开头导弹射程高度小的最大的导弹,删除这些导弹…...
深圳尚石设计有限公司/seo培训优化课程
万事开头难,之前一直做BLE(TI、Nordic、Dialog )相关开发,没有做过蓝牙音频相关的,现要做高通(CSR)QCC300x 、QCC302x、 QCC502x 系列开发,换了一个新的平台,不知道该从何…...
WordPress软件连接不了网站/怎样在平台上发布信息推广
算法简介 SPFA(Shortest Path Faster Algorithm)是Bellman-Ford算法的一种队列实现,减少了不必要的冗余计算。也有人说SPFA本来就是Bellman-Ford算法,现在广为流传的Bellman-Ford算法实际上是山寨版。 求单源最短路的SPFA算法的全称是:Short…...
百度网址大全在哪里找/东莞seo建站排名
原文链接:C11 Tutorial: Introducing the Move Constructor and the Move Assignment Operatorsmartbear.com由于本人才疏学浅,翻译难免有误,望各位不吝惜指正。右值引用右值引用(rvalue references)是一种新的用于绑定右值的引用类型。那么…...