Lake Counting积水问题 dfs深度搜索

我就是我 2023-07-04 12:35 15阅读 0赞

原题链接：[Lake Counting][]

## 深度优先搜索 ##

从任意w开始，把邻接部分全部用’.‘代替。一次DFS可以把初始和这个w连接的所有w替换为‘.’，直到兔子不存在w为止，总共次数也就是DFS的次数，即为原题中的水池个数。  
复杂度为O（8*N*M）=O（M\*N）。

#include <iostream>
    #include<cstdio>
    using namespace std;
    #define maxn 105
    char field[maxn][maxn];
    int n,m;
    void dfs(int x,int y)
    { 
        field[x][y]='.';
        //循环遍历八个方向
        for(int dx=-1;dx<=1;dx++){ 
            for(int dy=-1;dy<=1;dy++){ 
                int nx=x+dx,ny=y+dy;
                //判断(nx,ny)是否在园子里，以及是否有积水
                if(0<=nx&&nx<n&&0<=ny&&ny<m&&field[nx][ny]=='W'){ 
                    dfs(nx,ny);
                }
            }
        }
    }
    void solve()
    { 
        int res=0;
        for(int i=0;i<n;i++){ 
            for(int j=0;j<m;j++){ 
                if(field[i][j]=='W'){ 
                    //从有积水的地方开始深搜
                    dfs(i,j);
                    res++;
                }
            }
        }
        printf("%d\n",res);
    }
    int main()
    { 
        scanf("%d%d",&n,&m);
        for(int i=0;i<n;i++){ 
            for(int j=0;j<m;j++){ 
                cin>>field[i][j];
            }
        }
        solve();
        return 0;
    }

[Lake Counting]: http://poj.org/problem?id=2386

发表评论取消回复

表情：

评论列表（有 0 条评论，15人围观）

还没有评论，来说两句吧...

相关阅读

相关深度优先搜索（DFS）

文章目录一、简介二、DFS的代码实现三、代码测试一、简介深度优先搜索是一种常见的图搜索算法，它可以用于寻找图中从起点到终点的路径或遍历

小灰灰/ 2024年03月22日 14:50/ 0 赞/ 122 阅读

相关 Lake Counting积水问题 dfs深度搜索

原题链接：[Lake Counting][] 深度优先搜索从任意w开始，把邻接部分全部用’.‘代替。一次DFS可以把初始和这个w连接的所有w替换为‘.’，直到兔子不存

我就是我/ 2023年07月04日 12:35/ 0 赞/ 16 阅读

相关 DFS（深度优先搜索）---城堡问题

题目描述： ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9n

野性酷女/ 2023年06月25日 12:27/ 0 赞/ 57 阅读

相关 DFS（深度优先搜索）

深度优先搜索算法（Depth-First-Search），是搜索算法的一种。它沿着树的深度遍历树的节点，尽可能深的搜索树的分支。当节点v的所有边都己被探寻过，搜索将回溯到发现节

缺乏、安全感/ 2022年10月30日 04:26/ 0 赞/ 216 阅读

相关 POJ 2386 Lake Counting（经典dfs）

Lake Counting Time Limit: 1000MS Memory Limit: 65536K Total Submissions: 33538 Accep

系统管理员/ 2022年09月30日 13:53/ 0 赞/ 21 阅读

相关深度优先搜索DFS（迷宫问题）

问题及代码：给出迷宫的图纸和初始终点位置，用DFS求最小步数。 include <iostream> using namespace std; i

r囧r小猫/ 2022年07月28日 04:10/ 0 赞/ 177 阅读

相关 POJ 2386 Lake Counting【DFS】

Lake Counting Description Due to recent rains, water has pooled in various places i

野性酷女/ 2022年06月17日 00:37/ 0 赞/ 128 阅读

相关深度优先搜索（DFS）

DFS是相对于BFS的另一个中图搜索算法，其与BFS最大的不同在于它是深度优先，它会优先顺着一条路径走到底，一旦某个节点邻接的节点都被发现了，就会回溯到前面一个节点，直

以你之姓@/ 2022年05月15日 01:13/ 0 赞/ 277 阅读

相关 G - Lake Counting

题目描述： Due to recent rains, water has pooled in various places in Farmer John’s field,

待我称王封你为后i/ 2022年03月20日 08:07/ 0 赞/ 140 阅读

相关 Lake Counting

Description Due to recent rains, water has pooled in various places in Farmer John's fi

谁践踏了优雅/ 2021年06月24日 13:58/ 0 赞/ 268 阅读