
集训笔记---dfs(HDUOJ NO.1241 Oil Deposits )
读取输入并初始化变量 读取输入的网格数据 初始化计数器 遍历网格中的每个单元格 对于每个找到起点的单元格,执行DFS搜索 最终输出搜索结果 读取输入并初始化变量 读取网格数据并存储在二维数组 初始化计数器 遍历网格中的每一个单元格 对于每一个找到起点的单元格,执行DFS搜索 每次找到新的起点符号 最后输出搜索结果的总数
发布日期:2021-05-16 11:48:48
浏览次数:26
分类:精选文章
本文共 1470 字,大约阅读时间需要 4 分钟。
这是一道经典的深度优先搜索(DFS)题目,直接通过DFS算法即可解决问题。以下是实现代码和思路说明。
代码包含以下部分:
代码逻辑如下:
- 首先,读取网格的行数和列数
- 然后读取网格数据并存储在二维数组
grid
中 - 初始化一个计数器
count
来记录搜索结果的数量 - 遍历网格中的每一个单元格
- 对于每一个单元格,如果其值为起点符号
@
,则执行DFS搜索 - 在DFS搜索函数中,将当前单元格标记为已访问,递归搜索四个方向的相邻单元格
- 每次找到新的起点符号
@
,则递归调用DFS函数 - 最后输出搜索结果的总数
代码实现:
#include#include #include using namespace std;char grid[10][10];int rows, cols;void dfs(int x, int y) { grid[x][y] = '*'; //搜索四个方向 for (int dx = -1; dx <= 1; ++dx) { for (int dy = -1; dy <= 1; ++dy) { int nx = x + dx, ny = y + dy; if (nx >= 0 && nx < rows && ny >= 0 && ny < cols && grid[nx][ny] == '@') { dfs(nx, ny); } } }}int main() { //读取输入 while (scanf("%d %d", &rows, &cols)) { if (rows == 0 && cols == 0) { break; } char grid[rows][cols]; for (int i = 0; i < rows; ++i) { scanf("%s", grid[i]); } int count = 0; for (int i = 0; i < rows; ++i) { for (int j = 0; j < cols; ++j) { if (grid[i][j] == '@') { dfs(i, j); ++count; } } } printf("%d\n", count); } return 0;}
代码解释:
grid
中count
@
,则递归调用DFS函数这个代码实现了DFS算法,能够有效地解决问题。通过递归方式搜索网格中的起点符号@
,并标记访问过的单元格,避免重复计算。
发表评论
最新留言
能坚持,总会有不一样的收获!
[***.219.124.196]2025年04月29日 18时06分01秒
关于作者

喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
Linux系统中的日志文件(非常详细)零基础入门到精通,收藏这一篇就够了
2023-02-05
Linux系统中的系统盘和数据盘是什么意思?
2023-02-05
Linux系统中的默认安装目录 - 不能随意更改名字
2023-02-05
Linux系统中进程运行时间的五大精准检测法
2023-02-05
Linux系统中,shell脚本的异步执行
2023-02-05
Linux系统之软件管理:Ubuntu彻底删除软件及配置文件
2023-02-05
Linux系统信息查看命令
2023-02-05
Linux系统具体硬件型号查看与系统故障定位分析
2023-02-05
Linux系统初始化命令的备忘单,Linux运维工程师收藏!
2023-02-05
Linux系统启动流程
2023-02-05
Linux系统命令简单介绍
2023-02-05
Linux系统在线安装anaconda(Centos)
2023-02-05
Linux系统基本网络配置之ifconfig命令
2023-02-05
Linux系统基础-管理之加密、解密、Openssl基本应用及CA实现过程
2023-02-05
Linux系统大量的TIME_WAIT、CLOSE_WAIT连接问题解决
2023-02-05
linux系统如何实现内网穿透、外网访问
2023-02-05
linux系统如何实现内网穿透、外网访问
2023-02-05
Linux系统如何显示系统内存使用情况,free命令来了!
2023-02-05
linux系统如何进入屏保,linux上屏保设置
2023-02-05