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

红与黑(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查找 模版解读 错误示范 在之前的博客当中&#xff0c;详细地介绍了这类题目的解法&#xff0c;今天为大家带来一道类似的题目练练手&#xff0c;后续还会更新更有挑战的题目…...

为何学linux及用处

目前企业使用的操作系统无非就是国产类的&#xff0c;windows和linux类。我们要提升自己的技能&#xff0c;需要学习这两款。我记得在大学时期&#xff0c;学习过windows以及linux&#xff0c;但当时觉得又不常用&#xff0c;就学的模棱两可。毕业之后&#xff0c;你会发现&…...

ChatGPT高级数据分析功能

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

共享WiFi贴项目怎么实施与运营,微火为你提供高效解答!

共享WiFi贴是一项有前景的商业项目&#xff0c;不仅可以满足用户对网络的需求&#xff0c;还可以为创业者带来盈利的机会。那么&#xff0c;我们来看看如何有效地开展共享WiFi贴项目。 最重要的是选择合适的位置。共享WiFi贴项目的成功与否很大程度上取决于位置选择。优先选择人…...

计算机组成原理——基础入门总结(二)

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

腾讯mini项目-【指标监控服务重构】2023-08-06

今日已办 feature/client_traces_profile 修改 consumer 4个阶段的 spankind将 profile 的 span 作为 root span&#xff0c;保持与 venus 的 follows from 的 link feature/profile-otelclient-metric 将 metric 部分使用新分支 push go.opentelemetry.io/otel/propagatio…...

ruoyi菜单折叠,菜单收缩

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

Linux 用户和用户组

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

JavaBean文字格斗游戏(面向对象编程)的个人重写以及个人解释

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

动态面板案例分析

动态面板模型分析 如果在面板模型中&#xff0c;解释变量包括被解释变量的滞后值&#xff0c;此时则称之为“动态面板模型”&#xff0c;其目的是处理内生性问题。动态面板模型发展分为3个阶段&#xff0c;第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. 回顾数值型基本数据类型共有哪些&#xff1f; 2. 什么时候进行隐式类型转换&#xff1f; 3. 数据类型的隐式转换规则 4. 特殊隐式转换规则需牢记 5. 隐式转换小练习 5.1 byte 与 byte 如何转&#xff1f; 5.2 int&#xff0c;long&#xff0c;double 的转换 5.…...

Hbuilder本地调试微信H5项目(一)

摘要 通过内网穿透&#xff0c;访问本地Hbuilder创建的Vue项目 前置准备 下载并安装【HBuilder】&#xff0c;本文用的是HBuilder3.8.12版本&#xff0c;下载地址 下载并安装【微信开发者工具】&#xff0c;本文用的是1.06版本&#xff0c;下载地址 下载并安装【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类图中&#xff0c;类使用包含类名、属性、方法 属性或方法前的加好和减号表示了这个方法的可见性&#xff0c;可见性的符号有三种&#xff1a; 表示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>…...

面向对象的分析与设计(精品课程)第一章作业

面向对象的分析与设计&#xff08;精品课程&#xff09;第一章作业 一. 单选题&#xff08;共2题&#xff0c;18分&#xff09;二. 多选题&#xff08;共3题&#xff0c;27分&#xff09;三. 填空题&#xff08;共5题&#xff0c;45分&#xff09;四. 简答题&#xff08;共1题&…...

要使用API接口获取淘宝电商平台的数据,您需要遵循以下步骤:

了解API文档和规范&#xff1a;首先&#xff0c;您需要了解淘宝电商平台的API文档和规范&#xff0c;以确定可用的接口和参数。您可以在淘宝开放平台的官方文档中找到这些信息。注册并获取API密钥&#xff1a;在使用API之前&#xff0c;您需要在淘宝开放平台注册并获取API密钥。…...

vue中动态style(如何动态修改伪元素样式)

vue中动态style(如何动态修改伪元素样式)_vue怎么在行内给伪元素加样式_爱上星星的鲸鱼的博客-CSDN博客...

碳当量及相关指数

声明 本文是学习GB-T 713.1-2023 承压设备用钢板和钢带 第1部分&#xff1a;一般要求. 而整理的学习笔记,分享出来希望更多人受益,如果存在侵权请及时联系我们 1 范围 本文件规定了承压设备用钢板和钢带的牌号表示方法、订货内容、尺寸、外形、重量、技术要求、检验 规则、…...

生成xcframework

打包 XCFramework 的方法 XCFramework 是苹果推出的一种多平台二进制分发格式&#xff0c;可以包含多个架构和平台的代码。打包 XCFramework 通常用于分发库或框架。 使用 Xcode 命令行工具打包 通过 xcodebuild 命令可以打包 XCFramework。确保项目已经配置好需要支持的平台…...

从WWDC看苹果产品发展的规律

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

《用户共鸣指数(E)驱动品牌大模型种草:如何抢占大模型搜索结果情感高地》

在注意力分散、内容高度同质化的时代&#xff0c;情感连接已成为品牌破圈的关键通道。我们在服务大量品牌客户的过程中发现&#xff0c;消费者对内容的“有感”程度&#xff0c;正日益成为影响品牌传播效率与转化率的核心变量。在生成式AI驱动的内容生成与推荐环境中&#xff0…...

相机Camera日志分析之三十一:高通Camx HAL十种流程基础分析关键字汇总(后续持续更新中)

【关注我,后续持续新增专题博文,谢谢!!!】 上一篇我们讲了:有对最普通的场景进行各个日志注释讲解,但相机场景太多,日志差异也巨大。后面将展示各种场景下的日志。 通过notepad++打开场景下的日志,通过下列分类关键字搜索,即可清晰的分析不同场景的相机运行流程差异…...

SpringTask-03.入门案例

一.入门案例 启动类&#xff1a; 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 的类型推断会根据变量、函数返回值、对象和数组的赋值和使用方式&#xff0c;自动确定它们的类型。 这一特性减少了显式类型注解的需要&#xff0c;在保持类型安全的同时简化了代码。通过分析上下文和初始值&#xff0c;TypeSc…...

华为OD机试-最短木板长度-二分法(A卷,100分)

此题是一个最大化最小值的典型例题&#xff0c; 因为搜索范围是有界的&#xff0c;上界最大木板长度补充的全部木料长度&#xff0c;下界最小木板长度&#xff1b; 即left0,right10^6; 我们可以设置一个候选值x(mid)&#xff0c;将木板的长度全部都补充到x&#xff0c;如果成功…...

针对药品仓库的效期管理问题,如何利用WMS系统“破局”

案例&#xff1a; 某医药分销企业&#xff0c;主要经营各类药品的批发与零售。由于药品的特殊性&#xff0c;效期管理至关重要&#xff0c;但该企业一直面临效期问题的困扰。在未使用WMS系统之前&#xff0c;其药品入库、存储、出库等环节的效期管理主要依赖人工记录与检查。库…...

ThreadLocal 源码

ThreadLocal 源码 此类提供线程局部变量。这些变量不同于它们的普通对应物&#xff0c;因为每个访问一个线程局部变量的线程&#xff08;通过其 get 或 set 方法&#xff09;都有自己独立初始化的变量副本。ThreadLocal 实例通常是类中的私有静态字段&#xff0c;这些类希望将…...