java dfs

矫情吗；* 2022-08-17 14:15 116阅读 0赞

/\*  
\* Lake Counting  
Time Limit: 1000MS Memory Limit: 65536K  
Total Submissions: 25214 Accepted: 12701  
Description

Due to recent rains, water has pooled in various places in Farmer John’s field, which is  
represented by a rectangle of N x M (1 <= N <= 100; 1 <= M <= 100) squares. Each square  
contains either water (‘W’) or dry land (‘.’). Farmer John would like to figure out how  
many ponds have formed in his field. A pond is a connected set of squares with water in  
them, where a square is considered adjacent to all eight of its neighbors.

Given a diagram of Farmer John’s field, determine how many ponds he has.  
Input

*  Line 1: Two space-separated integers: N and M
 *  Lines 2..N+1: M characters per line representing one row of Farmer John’s field. Each
 *  character is either ‘W’ or ‘.’. The characters do not have spaces between them.  
    Output
 *  Line 1: The number of ponds in Farmer John’s field.  
    Sample Input

10 12  
W……..WW.  
.WWW…..WWW  
….WW…WW.  
………WW.  
………W..  
..W……W..  
.W.W…..WW.  
W.W.W…..W.  
.W.W……W.  
..W…….W.  
Sample Output

3  
Hint

OUTPUT DETAILS:

There are three ponds: one in the upper left, one in the lower left,and one along the right  
side.  
\* \*/

注意区分Java与c++的区别：
    1.Java没有全局变量的概念，与之等价的是类变量
    2.Java中的scanner不能输入一个字符，可以用scanner.next()再进行适当的转换得到。
    3.将字符串转为用字符数组存储，调用str.toCharArray();
    import java.security.PublicKey;
    import java.util.Scanner;
    4.可以将全局变量，被调用函数写在一个类（class global）里然后直接调用类变量，类方法即可
    
    import org.omg.CORBA.PUBLIC_MEMBER;
    
    class g_Var{   
        public static int n,m;
        public static char pools[][] = new char[110][110];
        public static void dfs(int x,int y){
            pools[x][y] = '.';
            for(int i=-1;i<=1;i++){
                for(int j=-1;j<=1;j++){
                    int nx=x+i,ny=y+j;
                    if(nx>=0&&nx<n&&ny>=0&&ny<m&&pools[nx][ny]=='W'){
                        dfs(nx, ny);
                    }
                }
            }
            return;
        }
    }  
    
    
    public class Main{
    
        public static void main(String[] args){
            Scanner sc = new Scanner(System.in);
            int cnt;
            g_Var.n = sc.nextInt();//通过类名操作类变量
            g_Var.m = sc.nextInt();
            String str;
            /*java中没有读入单个字符的方法。但可以转换 如：String s=scanner.next(); char c=s.charAt(0) * 关键在于如何将读入的数据进行转换为char*/
            for(int i=0;i<g_Var.n;i++){
                str = sc.next();
                g_Var.pools[i] = str.toCharArray();//调用函数转换为char数组
            }
            cnt = 0;
            for(int i=0;i<g_Var.n;i++){
                for(int j=0;j<g_Var.m;j++){
                    if(g_Var.pools[i][j]=='W'){
                        g_Var.dfs(i, j);
                        cnt++;
                    }
                }
            }
            System.out.println(cnt);
        }
    }

/\*\*  
\*  
\* 水池数目  
时间限制：3000 ms | 内存限制：65535 KB  
难度：4

描述  
南阳理工学院校园里有一些小河和一些湖泊，现在，我们把它们通一看成水池，假设有一张我们学校的某处的地图，这个地图上仅标识了  
此处是否是水池，现在，你的任务来了，请用计算机算出该地图中共有几个水池。

输入  
第一行输入一个整数N，表示共有N组测试数据  
每一组数据都是先输入该地图的行数m(0

import java.security.PublicKey;
    import java.util.Scanner;
    
    import org.omg.CORBA.PUBLIC_MEMBER;
    
    class g_Var{   
        public static int n,m;
        public static int pools[][] = new int[110][110];
        final static int dirx[]={-1,1,0,0},diry[]={
       0,0,-1,1};
        public static void dfs(int x,int y){
            pools[x][y] = 0;
            for(int i=0;i<4;i++){
                int nx=x+g_Var.dirx[i],ny=y+g_Var.diry[i];
                if(nx>=0&&nx<g_Var.n&&ny>=0&&ny<g_Var.m&&g_Var.pools[nx][ny]==1){
                    dfs(nx, ny);
                }
            }
            return;
        }
    }  
    
    public class Main { 
    
        public static void main(String[] args) {
            Scanner sc = new Scanner(System.in);
            int T = sc.nextInt();
            int cnt;
            while(T>=1){
                --T;
                g_Var.n = sc.nextInt();//通过类名操作类变量
                g_Var.m = sc.nextInt();
                for(int i=0;i<g_Var.n;i++){
                    for(int j=0;j<g_Var.m;j++){
                        g_Var.pools[i][j] = sc.nextInt();
                    }
                }
                cnt = 0;
                for(int i=0;i<g_Var.n;i++){
                    for(int j=0;j<g_Var.m;j++){
                        if(g_Var.pools[i][j]==1){
                            g_Var.dfs(i, j);
                            cnt++;
                        }
                    }
                }
                System.out.println(cnt);
            }
        }
    }