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

1818:红与黑【解析】-------深度优先搜索

1818:红与黑

描述

有一间长方形的房子,地上铺了红色、黑色两种颜色的正方形瓷砖。你站在其中一块黑色的瓷砖上,只能向相邻的黑色瓷砖移动。请写一个程序,计算你总共能够到达多少块黑色的瓷砖。

输入

包括多个数据集合。每个数据集合的第一行是两个整数W和H,分别表示x方向和y方向瓷砖的数量。W和H都不超过20。在接下来的H行中,每行包括W个字符。每个字符表示一块瓷砖的颜色,规则如下
1)‘.’:黑色的瓷砖;
2)‘#’:红色的瓷砖;
3)‘@’:黑色的瓷砖,并且你站在这块瓷砖上。该字符在每个数据集合中唯一出现一次。
当在一行中读入的是两个零时,表示输入结束。
输出
对每个数据集合,分别输出一行,显示你从初始位置出发能到达的瓷砖数(记数时包括初始位置的瓷砖)。

样例输入

6 9 
....#. 
.....# 
...... 
...... 
...... 
...... 
...... 
#@...# 
.#..#. 
0 0

样例输出

45

【题目解析】

本题需要求“@”所在的连通块大小。从起点开始,利用洪水填充法,将同一个连通块的瓷砖全部标记。根据模板框架,先界定清楚几个细节:
1.状态:描述当前局面情况的数学表示,一般是位置信息、时间信息等。在本题中,利用两个整数(x,y)表示当前所在的位置,表示当前在第x行、第y列。我们通常使用行列坐标,而不是坐标轴的坐标,以便于跟二维数组的下标对应起来。根据题意,起始状态便是“@”所在的位置。
2.标记:利用二维数组 v i s [ x ] [ y ] = t r u e vis[x][y]=true vis[x][y]=true,表示当前点(x,y)已经被染色。vis初始为 f a l s e false false,表示所有的点没有被染色。

代码如下:

#include<bits/stdc++.h>
using namespace std;
char a[21][21];
int w,h,cnt;
bool vis[21][21];
int dx[]={0,0,1,-1};
int dy[]={1,-1,0,0};void dfs(int x,int y){vis[x][y]=1;//当前点标记cnt++;for(int i=0;i<4;i++){int nx=x+dx[i];int ny=y+dy[i];if(nx<1||ny<1||nx>h||ny>w)continue;//出地图if(a[nx][ny]!='.')continue;//如果不是黑砖if(vis[nx][ny])continue;//已经在当前路径中dfs(nx,ny);}
}int main(){while(true){cin>>w>>h;if(!w&&!h)break;int sx=-1,sy=-1;for(int i=1;i<=h;i++){cin>>(a[i]+1);for(int j=1;j<=w;j++){if(a[i][j]=='@'){sx=i;sy=j;}}}if(sx==-1 && sy==-1){cout<<0<<endl;continue;}cnt=0;//多组数据需要把数组初始化memset(vis,false,sizeof(vis));dfs(sx,sy);cout<<cnt<<endl;}return 0;
}

在深度优先搜索的使用上还可以使用另外一种方式:

void dfs(int x,int y){for(int i=0;i<4;i++){int nx=x+dx[i];int ny=y+dy[i];if(nx<1||ny<1||nx>h||ny>w)continue;//出地图if(a[nx][ny]!='.')continue;if(vis[nx][ny])continue;//已经在当前路径中vis[nx][ny]=1;//标记cnt++;dfs(nx,ny);			        }
}

这种方式不会处理当前点的状态,使用原方式的main函数会缺少起始点的黑砖,所以需要对main函数进行修改。完整代码如下:

#include<bits/stdc++.h>
using namespace std;
char a[21][21];
int w,h,cnt;
bool vis[21][21];
int dx[]={0,0,1,-1};
int dy[]={1,-1,0,0};void dfs(int x,int y){for(int i=0;i<4;i++){int nx=x+dx[i];int ny=y+dy[i];if(nx<1||ny<1||nx>h||ny>w)continue;//出地图if(a[nx][ny]!='.')continue;if(vis[nx][ny])continue;//已经在当前路径中vis[nx][ny]=1;//标记cnt++;dfs(nx,ny);			        }
}int main(){while(true){cin>>w>>h;if(!w&&!h)break;int sx=-1,sy=-1;for(int i=1;i<=h;i++){cin>>(a[i]+1);for(int j=1;j<=w;j++){if(a[i][j]=='@'){sx=i;sy=j;cnt=1;//记录起始点的黑砖}}}if(sx==-1 && sy==-1){cout<<0<<endl;continue;}memset(vis,false,sizeof(vis));dfs(sx,sy);cout<<cnt<<endl;}return 0;
}

相关文章:

1818:红与黑【解析】-------深度优先搜索

1818:红与黑 描述 有一间长方形的房子&#xff0c;地上铺了红色、黑色两种颜色的正方形瓷砖。你站在其中一块黑色的瓷砖上&#xff0c;只能向相邻的黑色瓷砖移动。请写一个程序&#xff0c;计算你总共能够到达多少块黑色的瓷砖。 输入 包括多个数据集合。每个数据集合的第一行…...

实验三 Oracle数据库的创建和管理

&#x1f57a;作者&#xff1a; 主页 我的专栏C语言从0到1探秘C数据结构从0到1探秘Linux &#x1f618;欢迎关注&#xff1a;&#x1f44d;点赞&#x1f64c;收藏✍️留言 &#x1f3c7;码字不易&#xff0c;你的&#x1f44d;点赞&#x1f64c;收藏❤️关注对我真的很重要&…...

Mysql:重点且常用的 SQL 标签整理

目录 1 <resultMap> 标签 2 <sql> 标签 3 <where> 标签 4 <if> 标签 5 <trim> 标签 6 <foreach> 标签 7 <set> 标签 1 <resultMap> 标签 比如以下代码&#xff1a; <resultMap type"SysCollege" id&qu…...

云锁防火墙编译安装nginx-plugin模块

一般情况下&#xff0c;当用户安装云锁的时候&#xff0c;云锁会自动适配nginx版本&#xff0c;使用我们已经预编译好的包含云锁模块的nginx备份并替换掉您当前系统中使用的nginx。卸载时&#xff0c;会将系统原始nginx文件替换回来。因此&#xff0c;云锁可保护使用nginx搭建的…...

【服务器数据恢复】服务器迁移数据时lun数据丢失的数据恢复案例

服务器数据恢复环境&服务器故障&#xff1a; 一台安装Windows操作系统的服务器。工作人员在迁移该服务器中数据时突然无法读取数据&#xff0c;服务器管理界面出现报错。经过检查发现服务器中一个lun的数据丢失。 服务器数据恢复过程&#xff1a; 1、将故障服务器中所有磁盘…...

6.4.2转换文件

6.4.2转换文件 利用Swf2VideoConverter2可以很方便地将Flash动画(*.swf)转换为其它的视频格式。 1&#xff0e;单击“添加”按钮&#xff0c;在弹出的下拉菜单中选择“添加文件”&#xff0c;在弹出的“Open Swf Files(打开Swf文件)”窗口中选择swf文件(如&#xff1a;那些花…...

智能驾驶新浪潮:SSD与UFS存储技术如何破浪前行?-UFS篇

如果说SSD是赛道上的超级跑车&#xff0c;那UFS更像是专为智能汽车定制的高性能轻量化赛车。UFS采用串行接口技术&#xff0c;像是闪电侠一样&#xff0c;将数据传输的速度推向新高&#xff0c;大幅缩短了系统启动时间和应用程序加载时间&#xff0c;这对追求即时反应的ADAS系统…...

TS 学习笔录(持续更新中)

TS学习笔录 1、TS 数据类型有哪些&#xff1f;2、元组是什么&#xff1f;3、union&#xff08;联合类型&#xff09;& Literal&#xff08;字面量类型&#xff09;?4、any 和 unknown 的区别&#xff1f;5、Object 对象类型&#xff1f;6、type 、interface 、 class 之间…...

RabbitMQ安装和使用

简介 RabbitMQ是一套开源&#xff08;MPL&#xff09;的消息队列服务软件&#xff0c;是由LShift提供的一个Advanced Message Queuing Protocol (AMQP) 的开源实现&#xff0c;由以高性能、健壮以及可伸缩性出名的Erlang写成。所有主要的编程语言均有与代理接口通讯的客户端库…...

使用pyechart创建折线图

import json from pyecharts.charts import Line from pyecharts import options# 首先使用文件打开数据 f_us open(Desktop/python/Project/数据可视化/美国.txt,r,encoding"UTF-8") f_rb open(Desktop/python/Project/数据可视化/日本.txt,r,encoding"UTF-8…...

Vue3+Ts:使用i18n实现国际化与全局动态下拉框框切换语言

Vue3Ts&#xff1a;使用i18n实现国际化与全局动态下拉框框切换语言 一、下载依赖&#xff1a;二、创建ts文件并配置main.ts三&#xff0c;如何使用1.在<template>中使用2.在setup中使用 四、全局下拉框动态切换 一、下载依赖&#xff1a; npm install vue-i18nnex二、创…...

多目标优化中常用的差分进化算法DE【2】

# 多目标优化中常用的进化算法 1、链接一 2、链接二 #后续继续补充多目标的差分进化算法MODE的应用 此链接介绍很详细&#xff0c;此处用来分享学习&#xff0c;后续有问题会继续进行补充。 如果你觉得不错&#xff0c;佛系随缘打赏&#xff0c;感谢&#xff0c;你的支持是…...

游卡:OceanBase在游戏核心业务的规模化降本实践

从 2023 年 9 月测试 OceanBase&#xff0c;到如今 3 个核心业务应用 OceanBase&#xff0c;国内最早卡牌游戏研发者之一的游卡仅用了两个月。是什么原因让游卡放弃游戏行业通用的 MySQL方案&#xff0c;选择升级至 OceanBase&#xff1f;杭州游卡网络技术有限公司&#xff08;…...

LightDB - oracle_fdw 过滤条件下推增强【24.1】

LightDB - oracle_fdw 过滤条件下推增强【24.1】 1. 字符串比较下推1.1 示例 2. 隐式转换下推2.1 示例 3. nvl 和trim 下推3.1 示例 LightDB 在24.1版本对oracle_fdw 的where下推进行了增强&#xff0c;新增对如下两种情况进行下推&#xff1a; 字符串比较下推&#xff0c;如 …...

【计算机网络】HTTP协议以及简单的HTTP服务器实现

文章目录 一、HTTP协议1.认识URL2.urlencode和urldecode3.HTTP协议格式4.HTTP的方法5.HTTP的状态码6.HTTP常见Header7.重定向8.长连接9.会话保持10.基本工具 二、简单的HTTP服务器实现1.err.hpp2.log.hpp3.procotol.hpp4.Sock.hpp5.Util.hpp6.httpServer.hpp7.httpServer.cc8.总…...

04 SpringBoot整合Druid/MyBatis/事务/AOP+打包项目

整合Druid 项目结构&#xff1a; 引入依赖&#xff1a; <?xml version"1.0" encoding"UTF-8"?> <project xmlns"http://maven.apache.org/POM/4.0.0"xmlns:xsi"http://www.w3.org/2001/XMLSchema-instance"xsi:schemaL…...

C++程序编译时的_GLIBCXX_USE_CXX11_ABI参数的值选择,适配昇腾Transformer推理加速库与LLM推理模型库

目录 2024/1/19日更新确定已安装G编译测试程序获取宏值安装对应的Transformer LLM推理模型库和Transformer推理加速库小结 2024/1/19日更新 具体使用cxx11abi0 还是cxx11abi1 可通过python命令查询 import torch torch.compiled_with_cxx11_abi()若返回True 则使用 cxx11abi1…...

什么是站群服务器?

网站群服务器是管理多个网站的强大工具&#xff0c;可以帮助站长轻松管理和维护多个网站&#xff0c;提高网站运营效率。在本文中&#xff0c;我们将讨论站点组服务器的优势&#xff0c;以及为什么它是网站管理员不可或缺的工具。 介绍站群服务器 网站群服务器是一个集中管理…...

《WebKit 技术内幕》之四(3): 资源加载和网络栈

3. 网络栈 3.1 WebKit的网络设施 WebKit的资源加载其实是交由各个移植来实现的&#xff0c;所以WebCore其实并没有什么特别的基础设施&#xff0c;每个移植的网络实现是非常不一样的。 从WebKit的代码结构中可以看出&#xff0c;网络部分代码的确比较少的&#xff0c;它们都在…...

vue3-模板引用

//1.调用ref函数 -> ref对象 const h1Ref ref(null) const comRef ref(null) //组件挂载完毕之后才能获取 onMounted(()>{console.log(h1Ref.value);console.log(comRef.value); })<div class"father"><!-- 通过ref标识绑定ref对象 --><h2 re…...

Qt/C++开发监控GB28181系统/取流协议/同时支持udp/tcp被动/tcp主动

一、前言说明 在2011版本的gb28181协议中&#xff0c;拉取视频流只要求udp方式&#xff0c;从2016开始要求新增支持tcp被动和tcp主动两种方式&#xff0c;udp理论上会丢包的&#xff0c;所以实际使用过程可能会出现画面花屏的情况&#xff0c;而tcp肯定不丢包&#xff0c;起码…...

线程同步:确保多线程程序的安全与高效!

全文目录&#xff1a; 开篇语前序前言第一部分&#xff1a;线程同步的概念与问题1.1 线程同步的概念1.2 线程同步的问题1.3 线程同步的解决方案 第二部分&#xff1a;synchronized关键字的使用2.1 使用 synchronized修饰方法2.2 使用 synchronized修饰代码块 第三部分&#xff…...

测试markdown--肇兴

day1&#xff1a; 1、去程&#xff1a;7:04 --11:32高铁 高铁右转上售票大厅2楼&#xff0c;穿过候车厅下一楼&#xff0c;上大巴车 &#xffe5;10/人 **2、到达&#xff1a;**12点多到达寨子&#xff0c;买门票&#xff0c;美团/抖音&#xff1a;&#xffe5;78人 3、中饭&a…...

成都鼎讯硬核科技!雷达目标与干扰模拟器,以卓越性能制胜电磁频谱战

在现代战争中&#xff0c;电磁频谱已成为继陆、海、空、天之后的 “第五维战场”&#xff0c;雷达作为电磁频谱领域的关键装备&#xff0c;其干扰与抗干扰能力的较量&#xff0c;直接影响着战争的胜负走向。由成都鼎讯科技匠心打造的雷达目标与干扰模拟器&#xff0c;凭借数字射…...

代理篇12|深入理解 Vite中的Proxy接口代理配置

在前端开发中,常常会遇到 跨域请求接口 的情况。为了解决这个问题,Vite 和 Webpack 都提供了 proxy 代理功能,用于将本地开发请求转发到后端服务器。 什么是代理(proxy)? 代理是在开发过程中,前端项目通过开发服务器,将指定的请求“转发”到真实的后端服务器,从而绕…...

纯 Java 项目(非 SpringBoot)集成 Mybatis-Plus 和 Mybatis-Plus-Join

纯 Java 项目&#xff08;非 SpringBoot&#xff09;集成 Mybatis-Plus 和 Mybatis-Plus-Join 1、依赖1.1、依赖版本1.2、pom.xml 2、代码2.1、SqlSession 构造器2.2、MybatisPlus代码生成器2.3、获取 config.yml 配置2.3.1、config.yml2.3.2、项目配置类 2.4、ftl 模板2.4.1、…...

基于IDIG-GAN的小样本电机轴承故障诊断

目录 🔍 核心问题 一、IDIG-GAN模型原理 1. 整体架构 2. 核心创新点 (1) ​梯度归一化(Gradient Normalization)​​ (2) ​判别器梯度间隙正则化(Discriminator Gradient Gap Regularization)​​ (3) ​自注意力机制(Self-Attention)​​ 3. 完整损失函数 二…...

【学习笔记】erase 删除顺序迭代器后迭代器失效的解决方案

目录 使用 erase 返回值继续迭代使用索引进行遍历 我们知道类似 vector 的顺序迭代器被删除后&#xff0c;迭代器会失效&#xff0c;因为顺序迭代器在内存中是连续存储的&#xff0c;元素删除后&#xff0c;后续元素会前移。 但一些场景中&#xff0c;我们又需要在执行删除操作…...

python爬虫——气象数据爬取

一、导入库与全局配置 python 运行 import json import datetime import time import requests from sqlalchemy import create_engine import csv import pandas as pd作用&#xff1a; 引入数据解析、网络请求、时间处理、数据库操作等所需库。requests&#xff1a;发送 …...

在 Spring Boot 中使用 JSP

jsp&#xff1f; 好多年没用了。重新整一下 还费了点时间&#xff0c;记录一下。 项目结构&#xff1a; pom: <?xml version"1.0" encoding"UTF-8"?> <project xmlns"http://maven.apache.org/POM/4.0.0" xmlns:xsi"http://ww…...