HDU1241 Oil Deposits（dfs+连通块问题）

浅浅的花香味﹌ 2022-10-30 01:25 111阅读 0赞

背景描述

ztw同志负责探测地下石油储藏.ztw现在在一块矩形区域探测石油.他通过专业设备，来分析每个小块中是否蕴藏石油.如果这些蕴藏石油的小方格相邻(横向相邻，纵向相邻，还有对角相邻)，那么它们被认为是同一油藏的一部分.在这块矩形区域，可能有很多油藏.你的任务是确定有多少不同的油藏.

输入

输入可能有多个矩形区域(即可能有多组测试)。每个矩形区域的起始行包含m和n，表示行和列的数量，1<=n，m<=100，如果m=0表示输入的结束，接下来是n行，每行m个字符.每个字符对应一个小方格，并且要么是‘\*’、代表没有油，要么是‘@’，表示有油.(注意多组数据，必要的数组要及时清空~)

输出

对于每一个矩形区域，输出油藏的数量.两个小方格是相邻的，当且仅当他们水平或者垂直或者对角线相邻(即8个方向)。

示例输入

1 1

3 5

\*@\*@\*

\*\*@\*\*

\*@\*@\*

1 8

@@\*\*\*\*@\*

5 5

\*\*\*\*@

\*@@\*@

\*@\*\*@

@@@\*@

@@\*\*@

0 0

示例输出

代码：

import java.util.Scanner;
    
    public class Main{
            static int n,m,cnt;
            static final int N=105;
            static char map[][]=new char[N][N];
            static int dx[]={0,0,1,-1, 1,-1,1,-1};
            static int dy[]={1,-1,0,0,1,-1,-1,1};
            static void dfs(int x,int y){
                    if(map[x][y]=='@'){
                            map[x][y]='*';
                    }
                    for(int i=0;i<8;i++){
                            int xx=x+dx[i];
                            int yy=y+dy[i];
                            if(xx<0 ||yy<0 ||xx>=n ||yy>=m) continue;
                            if(map[xx][yy]=='*') continue;
                            dfs(xx,yy);
                    }
            }
            public static void main(String[] args) {
                    Scanner scan=new Scanner(System.in);
                    while(scan.hasNext()){
                            n=scan.nextInt();
                            m=scan.nextInt();
                            if(n==0 && m==0) break;
                            for(int i=0;i<n;i++){
                                    map[i]=scan.next().toCharArray();
                            }
                            cnt=0;
                            for(int i=0;i<n;i++)
                                for(int j=0;j<m;j++)
                                    if(map[i][j]=='@'){
                                            dfs(i,j);
                                            cnt++;
                                    }        
                            System.out.println(cnt);
                    }
            }
    }