P1451 求细胞数量

时间:2023-01-11 19:46:54

题目描述

一矩形阵列由数字0到9组成,数字1到9代表细胞,细胞的定义为沿细胞数字上下左右若还是细胞数字则为同一细胞,求给定矩形阵列的细胞个数。(1<=m,n<=100)?

 

输入输出格式

输入格式:

 

输入:整数m,n(m行,n列)

矩阵

 

输出格式:

 

输出:细胞的个数

 

BFS新手入门

这是一题裸得十分善良的搜索(善良到无记忆深搜都能快乐AC)


正片:

1.题意阅读:(读入)

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

这就意味着其实这题的读入只有两种分化

①没有细胞②有细胞(熟悉的bool数据)

所以在读入时我们就可以直接进行预处理

if(有细胞)

a[i][j]=1;

else

a[i][j]=0;

2.核心算法:(BFS)

BFS的核心就是找到一个合法节点后将其往外展开,判断后压如队列 (其实我也解释不清,还是看代码意会吧。。。)

//q[..][2]这是一个数组模拟的队列
//c[..][..]是方向数组
void bfs(int i,int j){//发现a[i][j]合法后的处理
    int head=0,tail=1;
    ans++;
    //一个新的细胞
    q[head][0]=i;
    q[head][1]=j;
    //将此合法点作为队首进行记录
    while(head<tail){//队伍搜完了,完整细胞已完全展开
        i=q[head][0];j=q[head][1];
        //队首弹出搜索
        for(int k=0;k<4;++k){
            if(a[i+c[k][0]][j+c[k][1]]){
            //如果这个节点可以访问
                q[tail][0]=i+c[k][0];
                q[tail][1]=j+c[k][1];
                a[q[tail][0]][q[tail][1]]=0;
                //将已经放进队列等待搜索的数标记成不可走
                //这样就不会导致重复对一个节点的访问
                ++tail;
            }
        }
        ++head;//已搜索节点删除
    }//一口气搜到没有连接在一起的合法节点
}

这段代码中,蒟蒻是直接将 无细胞 与 已发现节点 归为不可走节点的,全部用a[..][..]进行保存,不过当题目搜索条件复杂时,还是推荐按照条件分类使用多个数组进行保存记录,这样比较清晰。

3.分析

仔细一想好像效率也没比DFS小多少

最后奉上丑陋代码:

#include<bits/stdc++.h>
#define ll long long
using namespace std;
bool a[201][201];
int q[100005][2];
ll m,n,ans;
int c[4][2]={0,1,-1,0,1,0,0,-1};
void bfs(int i,int j){
    int head=0,tail=1;
    ans++;
    q[head][0]=i;
    q[head][1]=j;
    while(head<tail){
        i=q[head][0];j=q[head][1];
        for(int k=0;k<4;++k){
            if(a[i+c[k][0]][j+c[k][1]]){
                q[tail][0]=i+c[k][0];
                q[tail][1]=j+c[k][1];
                a[q[tail][0]][q[tail][1]]=0;
                ++tail;
            }
        }
        ++head;
    }
}
int main(){
    cin>>m>>n;
    char b;
    for(int i=1;i<=m;++i){
        for(int j=1;j<=n;++j){
            cin>>b;
            if(b=='0')
            a[i][j]=0;
            else
            a[i][j]=1;
        }
    }

    for(int i=1;i<=m;++i){
        for(int j=1;j<=n;++j){
            if(a[i][j]){
                bfs(i,j);
            }
        }
    }
    cout<<ans<<endl;

} 

恳请指点鸭     O(∩_∩)O