编程练习-2022-05-09-Andy

题目

清明时节雨纷纷，路上都是大水坑。已知一张地面的俯视图照片，请计算机智能识别出有几块独立的水坑。照片用n*m个像素的点阵组成，‘.’代表干区，‘@’代表有水。如果两个‘@’是（八个方向）相邻的，那么他们属于同一个水坑。如果一个‘@’独立出现，也代表一个水坑。

标签

DFS DFS八连通 465

AC代码

#include <bits/stdc++.h>
using namespace std;
int area,dx[10]={0,1,1,1,0,0,-1,-1,-1},dy[10]={0,1,0,-1,1,-1,1,0,-1},n,m;
char a[100][100];
void dfs(int d,int f){
    a[d][f]='.';
    for(int k=1;k<=8;k++){
        int nd=d+dx[k],nf=f+dy[k];
        if(nd>=1&&nd<=n&&nf>=1&&nf<=m&&a[nd][nf]=='@'){
            dfs(nd,nf);
        }
    }
}
int main()
{
    freopen("puddle.in","r",stdin);
    freopen("puddle.out","w",stdout);
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            cin>>a[i][j];
    int ans=0;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            if(a[i][j]=='@'){
                dfs(i,j);
                ans++;
            }
    cout<<ans;
    return 0;
}