水洼数目

朴灿烈づ我的快乐病毒、 2021-09-28 19:50 356阅读 0赞

题目: 有一个大小为N\*M的园子, 雨后起了积水，八连通的积水被认为是连接在一起的。请求出园子里总共有多少水洼.如下列字符组成的图,可以看出有两个水洼。

![20190529213929537.png][]

使用深度优先搜索(DFS), 在某一处水洼, 从8个方向查找, 直到找到所有连通的积水. 再次指定下一个水洼, 直到没有水洼为止。

输入数据:
    5 5
    ...WW
    WWWW.
    ...W.
    W....
    WWW..
    
    public class dfs_水洼数目 {
        static int M,N;
        public static void main(String[] args) {
            Scanner sc = new Scanner(System.in);
            M = sc.nextInt();
            N = sc.nextInt();
            char[][] arr = new char[M][N];
            for(int i=0;i<M;i++) {
                arr[i] = sc.next().toCharArray();
            }
            int count = 0;
            for(int i=0;i<M;i++) {
                for(int j=0;j<N;j++) {
                    if(arr[i][j]=='W') {
                        dfs(arr,i,j);//清除一个水洼
                        count++;
                    }
                }
            }
            System.out.println(count);
        }
        
        
        static void dfs(char[][] A,int i,int j) {
            A[i][j] = '.';
            //对八个方向进行移动,即使i/j分别加上-1,0,1   特别的,当i/j分别加上0时此点不移动
            for(int x = -1;x<=1;x++) {
                for(int y = -1;y<=1;y++) {
                    if(x == 0 && y == 0)  continue;//除去本点
                    if(i+x>=0 && i+x<M && j+y>=0 &&  j+y<N) {//对某个点的八个方向进行遍历
                        if(A[i+x][j+y] ==  'W')dfs(A,i+x,j+y);
                    }
                }
            }
        }
    }

最后，请你熟记八个方向遍历的技巧，因为很多路径类的算法题都可以使用这个技巧。

[20190529213929537.png]: /images/20210920/6187d9e913bc420b982cd28f5e48e0bb.png

发表评论取消回复

表情：

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

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

相关阅读

相关机器人数目

问题：少年宫新近邮购了小机器人配件，共有3类。 AA 类含有：8个轮子，1 个传感器； BB 类含有: 6 个轮子，3 个传感器； CC 类含有：4 个轮子，4 个传

超、凢脫俗/ 2024年03月26日 12:07/ 0 赞/ 167 阅读

相关 DFS-求水洼的数目

题目：有一个大小为 NM 的园子，雨后积起了水。八连通的积水被认为是连接在一起的。请求出园子里总共有多少水洼？（八连通指的是下图中相对 W 的的部分） W

迈不过友情╰/ 2023年07月11日 15:02/ 0 赞/ 22 阅读

相关 ZZULIOJ 1822: 水水更健康

1822: 水水更健康 Time Limit: 1 Sec Memory Limit: 128 MB Submit: 171 Solved: 63 [Sub

忘是亡心i/ 2022年08月21日 06:53/ 0 赞/ 241 阅读

相关 pku 1017 水题不水

\include <iostream> using namespace std; int main() \{ int num, m, n, l, x, y, z;// m:1\

港控/mmm°/ 2022年08月13日 04:28/ 0 赞/ 268 阅读

相关等值数目

等值数目 Time Limit: 1000ms Memory limit: 65536K 有疑问？点这里^\_^ 题目描述已知两个整数数组f\[\]和g\[

野性酷女/ 2022年08月10日 04:53/ 0 赞/ 265 阅读

相关支配值数目

支配值数目 Time Limit: 1000ms Memory limit: 65536K 有疑问？点这里^\_^ 题目描述已知f\[\]与g\[\]两个整

短命女/ 2022年08月10日 04:53/ 0 赞/ 214 阅读

相关买不到的数目

小明开了一家糖果店。他别出心裁：把水果糖包成4颗一包和7颗一包的两种。糖果不能拆包卖。小朋友来买糖的时候，他就用这两种包装来组合。当然有些糖果数目是无法组合出

冷不防/ 2022年08月08日 13:55/ 0 赞/ 217 阅读

相关 hdoj 2404 Permutation Recovery【水水】

Permutation Recovery Time Limit: 10000/4000 MS (Java/Others) Memory Limit: 327

叁歲伎倆/ 2022年08月05日 08:58/ 0 赞/ 214 阅读

相关水池的数目

水池数目时间限制： 3000 ms | 内存限制： 65535 KB 难度： 4 描述 include <bits/stdc++.h>

今天药忘吃喽~/ 2022年07月14日 15:57/ 0 赞/ 256 阅读

相关水洼数目

题目: 有一个大小为N\M的园子, 雨后起了积水，八连通的积水被认为是连接在一起的。请求出园子里总共有多少水洼.如下列字符组成的图,可以看出有两个水洼。 ![20190529

朴灿烈づ我的快乐病毒、/ 2021年09月28日 19:50/ 0 赞/ 357 阅读