寒光博客

[挑战程序设计]水洼数目 dfs
题目大意 有一个大小为 N×M 的园子,雨后积起了水。八连通的积水被认为是连接在一起的。请求出 园子里总共有多少水...
扫描右侧二维码阅读全文
05
2019/08

[挑战程序设计]水洼数目 dfs

题目大意

有一个大小为 N×M 的园子,雨后积起了水。八连通的积水被认为是连接在一起的。请求出 园子里总共有多少水洼?(八连通指的是下图中相对 W 的*的部分)

***
*W*
***

限制条件

N, M ≤ 100

输入

N=10, M=12
园子如下图('W'表示积水, '.'表示没有积水)

W........WW.
.WWW.....WWW
....WW...WW.
.........WW.
.........W..
..W......W..
.W.W.....WW.
W.W.W.....W.
.W.W......W.
..W.......W.

输出

3

分析

此类问题 适合dfs。
采用深度优先搜索,从任意的w开始,不断把邻接的部分用'.'代替,1次DFS后与初始这个w连接的所有w就全都被替换成'.'(为了防止回溯搜索导致死循环,把已经扫到的洼地的水抽干),因此直到图中不再存在W为止,总共进行DFS的次数就是答案。8个方向对应8个状态转移,每个格子作为DFS的参数最多调用一次,因时间复杂度为O(8nm)=O(nm)
其中的状态转移写法比较妙~

代码

package BlueCup.Seven_recursion;

import java.util.Scanner;

public class Dfs3水洼的数目 {
    static int n,m;
    public static void main(String[] args) {
        Scanner cin =new Scanner(System.in);
         n=cin.nextInt();
         m=cin.nextInt();
        char [][] a=new char[n][];
        int cnt=0;
        for (int i = 0; i < n; i++) {
            a[i]=cin.next().toCharArray();
        }
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if(a[i][j]=='W') {
                    dfs(a, i, j);//清除一个水洼
                    cnt++;//计数
                }

            }
        }
        System.out.println(cnt);

    }

    private static void dfs(char[][] a, int i, int j) {
        a[i][j]='.';
        for (int k = -1; k <2 ; k++) {//-1 0 1  9种状态
            for (int l = -1; l <2 ; l++) {

                if(k==0&&l==0){ //不动的状态去除
                    continue;
                }
                if(i+k>=0&&i+k<=n-1&&j+l>=0&&j+l<=m-1){//边界检测 行 列 八个平行状态
                    if(a[i+k][j+l]=='W'){
                        dfs(a,i+k,j+l);
                    }
                }
            }
        }
    }
}
本文作者:Author:     文章标题:[挑战程序设计]水洼数目 dfs
本文地址:https://dxoca.cn/Algorithm/222.html       百度未收录
版权说明:若无注明,本文皆为“Dxoca's blog (寒光博客)”原创,转载请保留文章出处。
Last modification:August 7th, 2019 at 10:17 am
如果觉得我的文章对你有用,请随意赞赏

Leave a Comment

One comment

  1. Dxoca

    妙啊 妙~