集训笔记---dfs(HDUOJ NO.1241 Oil Deposits )
发布日期:2021-05-16 11:48:48 浏览次数:26 分类:精选文章

本文共 1470 字,大约阅读时间需要 4 分钟。

这是一道经典的深度优先搜索(DFS)题目,直接通过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函数
  • 最后输出搜索结果的总数
  • 这个代码实现了DFS算法,能够有效地解决问题。通过递归方式搜索网格中的起点符号@,并标记访问过的单元格,避免重复计算。

    上一篇:集训笔记---dfs(HDUOJ NO.1016 Prime Ring Problem )
    下一篇:集训笔记---队列应用(HDUOJ NO.1387 Team Queue )

    发表评论

    最新留言

    能坚持,总会有不一样的收获!
    [***.219.124.196]2025年04月29日 18时06分01秒

    关于作者

        喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
    -- 愿君每日到此一游!

    推荐文章