简单的连通块

变量

题目要求：定义长宽$N,M$，输入一个地图，长宽都$\le100$，则$maps[105][105]$即可。 此外，还需要$vis[105][105]$记录是否访问过，$fx[4]=\{1,0,-1,0 \},fy[4]=\{0,1,0,-1 \}$求$x,y$方向增减，$s$记录山的总数。

int n,m;//地图长宽
bool maps[105][105],vis[105][105];//造地图
char ch;//不想用字符
int s=0;//山的总数
int fx[4]={1,0,-1,0};//x坐标
int fy[4]={0,-1,0,1};//y坐标

主函数

负责输入，及寻找山和记录山的总数。

int main(){
    cin>>n>>m;
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            cin>>ch;
            if(ch=='#')maps[i][j]=1;//字符转布尔
            else if(ch=='-')maps[i][j]=0;//造山
        }
    }
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            if(maps[i][j]==1&&vis[i][j]==0){//找山
                dfs(i,j);
                s++;//找到就+1
            }
        }
    }
    cout<<s;//输出山的数量
}

DFS

四处寻找附近的山，再走过去继续找。

void dfs(int x,int y){
    vis[x][y]=1;//走过了
    for(int i=0;i<4;i++){//找附近的山
        int xx=x+fx[i];
        int yy=y+fy[i];
        if(xx>=0&&xx<=n&&yy>=0&&y<=m&&maps[xx][yy]==1&&vis[xx][yy]!=1){//在不在范围，是不是山，走没走过
            dfs(xx,yy);
        }
    }
}

AC code

#include<bits/stdc++.h>
using namespace std;
int n,m;//地图长宽
bool maps[105][105],vis[105][105];//造地图
char ch;
int s=0;//山的总数
int fx[4]={1,0,-1,0};//x坐标
int fy[4]={0,-1,0,1};//y坐标
void dfs(int x,int y){
    vis[x][y]=1;//走过了
    for(int i=0;i<4;i++){//找附近的山
        int xx=x+fx[i];
        int yy=y+fy[i];
        if(xx>=0&&xx<=n&&yy>=0&&y<=m&&maps[xx][yy]==1&&vis[xx][yy]!=1){//在不在范围，是不是山，走没走过
            dfs(xx,yy);
        }
    }
}
int main(){
    cin>>n>>m;
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            cin>>ch;
            if(ch=='#')maps[i][j]=1;
            else if(ch=='-')maps[i][j]=0;//造山
        }
    }
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            if(maps[i][j]==1&&vis[i][j]==0){//找山
                dfs(i,j);
                s++;//找到就+1
            }
        }
    }
    cout<<s;//输出山的数量
}