红与黑(bfs + dfs 解法)(算法图论基础入门)
红与黑问题
文章目录
- 红与黑问题
- 前言
- 问题描述
- bfs 解法
- dfs 解法
前言
献给阿尔吉侬的花束( 入门级bfs查找 + 模版解读 + 错误示范
在之前的博客当中,详细地介绍了这类题目的解法,今天为大家带来一道类似的题目练练手,后续还会更新更有挑战的题目以及更为详细的解析,喜欢的小伙伴可以点个关注啦!
问题描述
有一间长方形的房子,地上铺了红色、黑色两种颜色的正方形瓷砖。
你站在其中一块黑色的瓷砖上,只能向相邻(上下左右四个方向)的黑色瓷砖移动。
请写一个程序,计算你总共能够到达多少块黑色的瓷砖。
输入格式
输入包括多个数据集合。
每个数据集合的第一行是两个整数 W 和 H,分别表示 x 方向和 y 方向瓷砖的数量。
在接下来的 H 行中,每行包括 W 个字符。每个字符表示一块瓷砖的颜色,规则如下
1)‘.’:黑色的瓷砖;
2)‘#’:红色的瓷砖;
3)‘@’:黑色的瓷砖,并且你站在这块瓷砖上。该字符在每个数据集合中唯一出现一次。
当在一行中读入的是两个零时,表示输入结束。
输出格式
对每个数据集合,分别输出一行,显示你从初始位置出发能到达的瓷砖数(记数时包括初始位置的瓷砖)。
数据范围
1≤W,H≤20
输入样例:
6 9
....#.
.....#
......
......
......
......
......
#@...#
.#..#.
0 0
输出样例:
45
bfs 解法
话不多说,直接上代码,解析都在注释当中:
#include<iostream>
#include<cstring>
#include<queue>
using namespace std;
const int N = 23;
char g[N][N];
int h,w,ans;
typedef pair<int,int> PII;
int dx[4]={-1,0,1,0};
int dy[4]={0,1,0,-1};
void bfs(int x,int y){g[x][y]='#';queue<PII> q;q.push({x,y});//队列的初始化while(!q.empty()){auto t=q.front();q.pop();for(int i=0;i<4;i++){int a=t.first+dx[i];int b=t.second+dy[i];if(a>=1 && a<=h && b>=1 && b<=w && g[a][b]=='.'){q.push({a,b});ans++;g[a][b]='#';//把走过的路封死//防止重读走的现象}}}
}
int main(){while(cin>>w>>h,w||h){//注意这里的输入//宽和高要反着来int x,y;ans=0;for(int i=1;i<=h;i++){for(int j=1;j<=w;j++){cin>>g[i][j];if(g[i][j]=='@'){x=i,y=j;//找到其实方块}}}bfs(x,y);cout<<ans+1<<endl;//为什么要 +1 呢?//因为后续的bfs算法没有考虑最开始的那个方块}
}
dfs 解法
#include<iostream>
using namespace std;
const int N =23;
char g[N][N];
int ans,h,w;
int dx[4]={-1,0,1,0};
int dy[4]={0,1,0,-1};
void dfs(int x,int y){g[x][y]='#';for(int i=0;i<4;i++){int a=x+dx[i];int b=y+dy[i];if(x>=1 && x<= h && y>=1 && y<=w && g[a][b]=='.'){dfs(a,b);ans++;}}
}
int main(){while(cin>>w>>h,w||h){ans=0;int x,y;for(int i=1;i<=h;i++){for(int j=1;j<=w;j++){cin>>g[i][j];if(g[i][j]=='@'){x=i,y=j;}}}dfs(x,y);cout<<ans+1<<endl;}return 0;
}
相关文章:
红与黑(bfs + dfs 解法)(算法图论基础入门)
红与黑问题 文章目录 红与黑问题前言问题描述bfs 解法dfs 解法 前言 献给阿尔吉侬的花束( 入门级bfs查找 模版解读 错误示范 在之前的博客当中,详细地介绍了这类题目的解法,今天为大家带来一道类似的题目练练手,后续还会更新更有挑战的题目…...
为何学linux及用处
目前企业使用的操作系统无非就是国产类的,windows和linux类。我们要提升自己的技能,需要学习这两款。我记得在大学时期,学习过windows以及linux,但当时觉得又不常用,就学的模棱两可。毕业之后,你会发现&…...

ChatGPT高级数据分析功能
目录 只需上传数据集,系统即可自动进行分析。我们首先进行了一次测试。准备了一份关于二手车的数据,其格式如下: 接下来调用,GPT中的高级数据分析功能,上传数据,并要求进行分析 第一步:自动对数据字段进行详细的解释: 第二步,对数据进行预处理,比如缺失值,基本的…...

共享WiFi贴项目怎么实施与运营,微火为你提供高效解答!
共享WiFi贴是一项有前景的商业项目,不仅可以满足用户对网络的需求,还可以为创业者带来盈利的机会。那么,我们来看看如何有效地开展共享WiFi贴项目。 最重要的是选择合适的位置。共享WiFi贴项目的成功与否很大程度上取决于位置选择。优先选择人…...

计算机组成原理——基础入门总结(二)
上一期的路径:基础入门总结(一) 目录 一.输入输出系统和IO控制方式 二.存储系统的基本概念 三.cache的基本概念和原理 四.CPU的功能和基本结构 五.总线概述 一.输入输出系统和IO控制方式 IO设备又可以被统一称为外部设备~ IO接口&…...

腾讯mini项目-【指标监控服务重构】2023-08-06
今日已办 feature/client_traces_profile 修改 consumer 4个阶段的 spankind将 profile 的 span 作为 root span,保持与 venus 的 follows from 的 link feature/profile-otelclient-metric 将 metric 部分使用新分支 push go.opentelemetry.io/otel/propagatio…...

ruoyi菜单折叠,菜单收缩
问题描述 VUE菜单有一个BUG,当我们点击其它按钮或者首页的时候,已经展示的一级菜单是不会自动收缩的。这个问题也导致很多开发者把一级菜单都换成了二级菜单。 错误展示 错误的效果请看下图。 解决方法 1、寻找菜单文件 因为我使用的是ruoyi的前端框…...

Linux 用户和用户组
Linux中关于权限的管控级别有2个级别,分别是: 针对用户的权限控制 针对用户组的权限控制 比如,针对某文件,可以控制用户的权限,也可以控制用户组的权限。 1、用户组管理 1.1、创建用户组 groupadd 用户组名 1.2、删除用户组 groupdel 用户…...

JavaBean文字格斗游戏(面向对象编程)的个人重写以及个人解释
题目和个人思路: 先写role类(对象)和构造方法(要按照标准的JavaBean来写) 根据题意,类中要有一个行为(方法)->攻击 开始进入main中, 首先当然是要创建两个对象,然后调用(攻击)attack方法 以上都是个人经过学习后重新又写的代码. 望各位指出不足....

动态面板案例分析
动态面板模型分析 如果在面板模型中,解释变量包括被解释变量的滞后值,此时则称之为“动态面板模型”,其目的是处理内生性问题。动态面板模型发展分为3个阶段,第1阶段是由Arellano and Bond(1991)提出的差分GMM(difference GMM)&a…...

vuepress+gitee免费搭建个人博客(无保留版)
文章目录 最终效果,一睹为快!一、工具选型二、什么是VuePress三、准备工作3.1 node 安装3.2 Git安装3.3 Gitee账号注册四、搭建步骤4.1 初始化VuePress4.2 安装VuePress4.3 初始化目录4.4 编写文章五、部署到Gitee5.1 创建仓库5.2 个人空间地址设置4.3 推送本地博客项目到Git…...

Java中的隐式转换和强制转换底层是怎么做的?
目录 1. 回顾数值型基本数据类型共有哪些? 2. 什么时候进行隐式类型转换? 3. 数据类型的隐式转换规则 4. 特殊隐式转换规则需牢记 5. 隐式转换小练习 5.1 byte 与 byte 如何转? 5.2 int,long,double 的转换 5.…...

Hbuilder本地调试微信H5项目(一)
摘要 通过内网穿透,访问本地Hbuilder创建的Vue项目 前置准备 下载并安装【HBuilder】,本文用的是HBuilder3.8.12版本,下载地址 下载并安装【微信开发者工具】,本文用的是1.06版本,下载地址 下载并安装【natapp】&a…...

OPC DCOM快速配置
目录 1 老系统配置 1.1 移除Windows 安全 1.2 建立相互能识别的用户账号 1.3 配置系统宽泛的DCOM设置 1.4 配置Server的特殊DCOM设置 1.5 恢复Windows安全 1 老系统配置 远程OPC访问必须在服务器和客户端两端配置DCOM。本文讲述如何正确配置 DCOM 的步骤并保证安全。 新…...

软件设计模式
1.UML 1.1类图表示法 uml类图中,类使用包含类名、属性、方法 属性或方法前的加好和减号表示了这个方法的可见性,可见性的符号有三种: 表示public -表示private #表示protected 1.2 类与类之间关系 关联关系 单向关联 双向关系 自关联 聚合关…...
Git常见场景命令总结
1、查看远程仓库标签/分支 git ls-remote --tags origin git ls-remote --heads origin2、删除远程仓库标签/分支 git push origin --delete refs/tags/my_tag3、删除本地标签/分支 git branch -d <branch_name>4、修改代码但未add回滚 git checkout -- <file1>…...
面向对象的分析与设计(精品课程)第一章作业
面向对象的分析与设计(精品课程)第一章作业 一. 单选题(共2题,18分)二. 多选题(共3题,27分)三. 填空题(共5题,45分)四. 简答题(共1题&…...

要使用API接口获取淘宝电商平台的数据,您需要遵循以下步骤:
了解API文档和规范:首先,您需要了解淘宝电商平台的API文档和规范,以确定可用的接口和参数。您可以在淘宝开放平台的官方文档中找到这些信息。注册并获取API密钥:在使用API之前,您需要在淘宝开放平台注册并获取API密钥。…...
vue中动态style(如何动态修改伪元素样式)
vue中动态style(如何动态修改伪元素样式)_vue怎么在行内给伪元素加样式_爱上星星的鲸鱼的博客-CSDN博客...

碳当量及相关指数
声明 本文是学习GB-T 713.1-2023 承压设备用钢板和钢带 第1部分:一般要求. 而整理的学习笔记,分享出来希望更多人受益,如果存在侵权请及时联系我们 1 范围 本文件规定了承压设备用钢板和钢带的牌号表示方法、订货内容、尺寸、外形、重量、技术要求、检验 规则、…...
生成xcframework
打包 XCFramework 的方法 XCFramework 是苹果推出的一种多平台二进制分发格式,可以包含多个架构和平台的代码。打包 XCFramework 通常用于分发库或框架。 使用 Xcode 命令行工具打包 通过 xcodebuild 命令可以打包 XCFramework。确保项目已经配置好需要支持的平台…...

从WWDC看苹果产品发展的规律
WWDC 是苹果公司一年一度面向全球开发者的盛会,其主题演讲展现了苹果在产品设计、技术路线、用户体验和生态系统构建上的核心理念与演进脉络。我们借助 ChatGPT Deep Research 工具,对过去十年 WWDC 主题演讲内容进行了系统化分析,形成了这份…...

《用户共鸣指数(E)驱动品牌大模型种草:如何抢占大模型搜索结果情感高地》
在注意力分散、内容高度同质化的时代,情感连接已成为品牌破圈的关键通道。我们在服务大量品牌客户的过程中发现,消费者对内容的“有感”程度,正日益成为影响品牌传播效率与转化率的核心变量。在生成式AI驱动的内容生成与推荐环境中࿰…...
相机Camera日志分析之三十一:高通Camx HAL十种流程基础分析关键字汇总(后续持续更新中)
【关注我,后续持续新增专题博文,谢谢!!!】 上一篇我们讲了:有对最普通的场景进行各个日志注释讲解,但相机场景太多,日志差异也巨大。后面将展示各种场景下的日志。 通过notepad++打开场景下的日志,通过下列分类关键字搜索,即可清晰的分析不同场景的相机运行流程差异…...

SpringTask-03.入门案例
一.入门案例 启动类: package com.sky;import lombok.extern.slf4j.Slf4j; import org.springframework.boot.SpringApplication; import org.springframework.boot.autoconfigure.SpringBootApplication; import org.springframework.cache.annotation.EnableCach…...

【电力电子】基于STM32F103C8T6单片机双极性SPWM逆变(硬件篇)
本项目是基于 STM32F103C8T6 微控制器的 SPWM(正弦脉宽调制)电源模块,能够生成可调频率和幅值的正弦波交流电源输出。该项目适用于逆变器、UPS电源、变频器等应用场景。 供电电源 输入电压采集 上图为本设计的电源电路,图中 D1 为二极管, 其目的是防止正负极电源反接, …...
4. TypeScript 类型推断与类型组合
一、类型推断 (一) 什么是类型推断 TypeScript 的类型推断会根据变量、函数返回值、对象和数组的赋值和使用方式,自动确定它们的类型。 这一特性减少了显式类型注解的需要,在保持类型安全的同时简化了代码。通过分析上下文和初始值,TypeSc…...

华为OD机试-最短木板长度-二分法(A卷,100分)
此题是一个最大化最小值的典型例题, 因为搜索范围是有界的,上界最大木板长度补充的全部木料长度,下界最小木板长度; 即left0,right10^6; 我们可以设置一个候选值x(mid),将木板的长度全部都补充到x,如果成功…...

针对药品仓库的效期管理问题,如何利用WMS系统“破局”
案例: 某医药分销企业,主要经营各类药品的批发与零售。由于药品的特殊性,效期管理至关重要,但该企业一直面临效期问题的困扰。在未使用WMS系统之前,其药品入库、存储、出库等环节的效期管理主要依赖人工记录与检查。库…...
ThreadLocal 源码
ThreadLocal 源码 此类提供线程局部变量。这些变量不同于它们的普通对应物,因为每个访问一个线程局部变量的线程(通过其 get 或 set 方法)都有自己独立初始化的变量副本。ThreadLocal 实例通常是类中的私有静态字段,这些类希望将…...