dfs-池塘_牛客博客

链接：https://ac.nowcoder.com/acm/contest/26276/A 来源：牛客网由于最近的降雨，水在农民约翰的田地里的不同地方聚集起来，这片田地由一个长方形表示，长方形为N x M（1<=N<=100；1<=M<=100）正方形。每个广场都有水（“W”）或旱地（“W”）。农夫约翰想知道他的田地里形成了多少池塘。池塘是一组相互连接的广场，其中有水，其中一个广场被视为与其所有八个邻居相邻。给农民约翰的田地一张图表，确定他有多少池塘。输入描述: 第1行：两个空格分隔的整数：N和M*第2行。。每行N+1:M个字符，代表一排农民约翰的田地。每个字符都是“W”或“.”。字符之间没有空格。输出描述: 第1行：农夫约翰田里池塘的数量。

c
c++
python

#include <iostream>

#include <stdio.h>
void fun(int a,int b,int m,int n);
char ch[120][120];
int main()
{
    int s=0,m,n,i,j;
    scanf("%d %d",&m,&n);

    for(i=0;i<m;i++)
    {
        scanf("%s",ch[i]);
    }
    for(i=0;i<m;i++)
    {
        for(j=0;j<n;j++)
        {
            if(ch[i][j]=='W')
            {
                fun(i,j,m,n);
                s++;
            }
        }

    }
    printf("%d",s);
}
void fun(int a,int b,int m,int n)
{
    ch[a][b]='.';
    int i,j;
    for(i=-1;i<=1;i++)
    {
        for(j=-1;j<=1;j++)
        {
            if(a+i>=0&&b+j>=0&&ch[a+i][b+j]=='W'&&a+i<m&&b+j<n)
            {
                fun(a+i,b+j,m,n);
            }

        }
    }

}

#include <iostream>
using namespace std;
#include <string>
#include <algorithm>
#include <bits/stdc++.h>
char ch[100][110];
int a[6];
int n,m;
inline void dfs(int x,int y)//
{
    ch[x][y]='.';
    for(int x1=-1;x1<=1;x1++)
        for(int y1=-1;y1<=1;y1++)
        {
           int x2=x+x1,y2=y+y1;
           if(x2>=0&&x2<n&&y2>=0&&y2<m&&ch[x2][y2]=='W') dfs(x2,y2);
        }
}
inline void solve()
{
    int res=0;
    for(int i=0;i<n;i++)
        for(int j=0;j<m;j++)
            if(ch[i][j]=='W') 
            {
                dfs(i,j);
                    res++;
            }
    cout<<res;
}
int main()
{
    cin>>n>>m;
    for(int i=0;i<n;i++) cin>>ch[i];
    solve();
    return 0;
}

print('Hello world!')