acwing1097. 池塘计数

题目

农夫约翰有一片 N∗M 的矩形土地。

最近，由于降雨的原因，部分土地被水淹没了。

现在用一个字符矩阵来表示他的土地。

每个单元格内，如果包含雨水，则用”W”表示，如果不含雨水，则用”.”表示。

现在，约翰想知道他的土地中形成了多少片池塘。

每组相连的积水单元格集合可以看作是一片池塘。

每个单元格视为与其上、下、左、右、左上、右上、左下、右下八个邻近单元格相连。

请你输出共有多少片池塘，即矩阵中共有多少片相连的”W”块

题解

深搜

#include<iostream>
using namespace std;
const int N=1010;
char g[N][N];
int n,m,ans=0;
int dx[8]={1,0,-1,0,1,-1,-1,1};
int dy[8]={0,1,0,-1,1,-1,1,-1};
void dfs(int i,int j){
    for(int k=0;k<8;k++){
        int x=i+dx[k],y=j+dy[k];
        if(x>=0&&x<n&&y>=0&&y<m&&g[x][y]=='W'){
            g[x][y]='.';
            dfs(x,y);
        }
    }
}

int main(){
    cin>>n>>m;
    for(int i=0;i<n;i++)
        for(int j=0;j<m;j++)
            cin>>g[i][j];
    
    for(int i=0;i<n;i++)
        for(int j=0;j<m;j++)
            if(g[i][j]=='W'){
                g[i][j]='.';
                dfs(i,j);
                ans++;
            }
    cout<<ans<<endl;
    
    return 0;
}

广搜

#include<iostream>
#define x first
#define y second
using namespace std;
const int N=1010;
typedef pair<int ,int>PII;
PII q[N*N];

char g[N][N];
int n,m,ans=0;
int dx[8]={1,0,-1,0,1,-1,-1,1};
int dy[8]={0,1,0,-1,1,-1,1,-1};
void bfs(int i,int j){
    int hh=0,tt=0;
    q[0]={i,j};
    while(hh<=tt){
        PII t=q[hh++];
        for(int k=0;k<8;k++){
            int x=t.x+dx[k],y=t.y+dy[k];
            if(x<0||x>=n||y<0||y>=m||g[x][y]=='.')continue;
            q[++tt]={x,y};
            g[x][y]='.';
        }
    }
    
}

int main(){
    cin>>n>>m;
    for(int i=0;i<n;i++)
        for(int j=0;j<m;j++)
            cin>>g[i][j];
    
    for(int i=0;i<n;i++)
        for(int j=0;j<m;j++)
            if(g[i][j]=='W'){
                bfs(i,j);
                ans++;
            }
    cout<<ans<<endl;
    
    return 0;
}