题目描述

$DFS和BFS的区别$

题目传送门

求细胞数量

题目描述

一矩形阵列由数字 $0$ 到 $9$ 组成，数字 $1$ 到 $9$ 代表细胞，细胞的定义为沿细胞数字上下左右若还是细胞数字则为同一细胞，求给定矩形阵列的细胞个数。

输入格式

第一行两个整数代表矩阵大小 $n$ 和 $m$。

接下来 $n$ 行，每行一个长度为 $m$ 的只含字符 0 到 9 的字符串，代表这个 $n \times m$ 的矩阵。

输出格式

一行一个整数代表细胞个数。

样例 #1

样例输入 #1

4 10
0234500067
1034560500
2045600671
0000000089

样例输出 #1

4

提示

数据规模与约定

对于 $100\%$ 的数据，保证 $1 \le n,m \le 100$。

no.1

DFS

首先声明

用scanf读入整数的时候可以控制读入的位数，比如scanf(“%1d”,&m);

深搜，不多讲，直接暴力

#include<bits/stdc++.h> 
using namespace std;
int n,m,cnt;
int a[105][105];
bool used[105][105];
int dx[4]={-1,1,0,0};
int dy[4]={0,0,-1,1};
void dfs(int x,int y)
{
    used[x][y]=1;
    for(int i=0;i<4;i++)
    {
        int nx=x+dx[i];
        int ny=y+dy[i];
        if(a[nx][ny]==0 || used[nx][ny]==1) continue;
        dfs(nx,ny);
    }
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++) 
            scanf("%1d",&a[i][j]);
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            if(used[i][j]==0&&a[i][j]!=0)
            {
                dfs(i,j);
                cnt++;
            }
        }
    }
    cout<<cnt;  
}

no.2

BFS

用队列，直接填色一下,qwq

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,m;
int dx[]={-1,0,1,0};
int dy[]={0,1,0,-1};
int a[110][110];
bool used[110][110];
int ans;
void bfs(int x,int y){
    queue<int>xx,yy;
    xx.push(x);
    yy.push(y);
    a[x][y] = ans;
    used[x][y] = 1;
    while(!xx.empty())
    {
        for(int i=0;i<=3;i++)
        {
            int nx=xx.front()+dx[i];
            int ny=yy.front()+dy[i];
            if (nx>=1&&nx<=n&&ny>=1&&ny<=m&&a[nx][ny]!=0&&used[nx][ny]==0)
            {
                 xx.push(nx);
                 yy.push(ny);
                 a[nx][ny]=ans;
                 used[nx][ny]=1;
            }
        }
        xx.pop();
        yy.pop();
    }
}
signed main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            scanf("%1d",&a[i][j]);
        }
    } 
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            if(a[i][j]>0&&!used[i][j]){
                ++ans;
                bfs(i,j);
            }
        }
    }
    cout<<ans;
}