题解CF690D1 The Wall(easy)

thomas_zjl · 2023-03-13 20:09:58 · 题解

题目大意。

输入一个 R \times C 的矩阵，求他的连通块个数。

解题思路。

这是一道求连通块的模板题。

可以使用深度优先搜索来解决。

代码

//深搜。
#include<bits/stdc++.h>
using namespace std;
char a[101][101];
bool f[101][101];
int ans=0;
int n,m;
void dfs(int x,int y){
    if(x<1||y<1||x>n||y>m||f[x][y]){
        return;
    }
    f[x][y]=1;
    dfs(x+1,y);
    dfs(x-1,y);
    dfs(x,y-1);
    dfs(x,y+1); 
}
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            cin>>a[i][j];
            if(a[i][j]=='.'){
                f[i][j]=1;
            }
        }
    }
    int ans=0;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            if(!f[i][j]){
                ans++;
                dfs(i,j);
            }
        }
    } 
    cout<<ans;
    return 0;
}