广度优先搜索遍历2-一矩形阵列由数字0到9组成，数字1到9代表细胞，细胞的定义为沿细胞数字上下左右还是细胞数字则为同一细胞

曾经终败给现在 2023-07-06 04:56 3阅读 0赞

例8.2
    一矩形阵列由数字0到9组成，数字1到9代表细胞，细胞的定义为沿细胞数字上下左右还是细胞数字则为同一细胞，
    求给定矩形阵列的细胞个数
    
    分析
    1.从文件中读入m*n矩阵阵列，将其转换为boolean矩阵存入bz数组中
    2.沿bz数组矩阵从上到下、从左到右，找到遇到的第一个细胞
    3.将细胞的位置入队h,并沿其上下左右四个方向上的细胞位置入队，入对后的位置bz数组置为false
    4.将h队的队头出队，沿其上下左右四个方向上的细胞位置入队，入队后的位置bz数组置为false
    5.重复4中的操作，直至h队空为止，则此时找出了一个细胞
    6.重复2，直至矩阵找不到细胞
    7.输出找到的细胞数

#include<iostream>
    #include<bits/stdc++.h>
    using namespace std;
    
    int dx[4]={-1,0,1,0},dy[4]={0,1,0,-1};
    int bz[100][100],num=0,n,m;
    
    //广度优先搜索算法处理
    void doit(int p,int q){
        //初始化数据
        int x,y,t,w,i;
        int h[1000][3];
        num++;
        bz[p][q]=0;
        t=0;
        w=1;
        h[1][1]=p;//遇到的第一个细胞入队
        h[1][2]=q;
    
        //循环遍历
        do{
            t++;//队头指针加1
            //沿细胞的上下左右四个方向搜索细胞
            for (i = 0; i <=3; ++i) {
                x=h[t][1]+dx[i];//用于移动左右位置
                y=h[t][2]+dy[i];//用于移动上下位置
                //判断该点是否可以入队
                //前四个限制条件是必须在bz数组中，
                if((x>=0)&&(x<m)&&(y>=0)&&(y<n)&&(bz[x][y])){
                    w++;
                    h[w][1]=x;//将需要移动的位置记录进H表中
                    h[w][2]=y;
                    bz[x][y]=0;//记录走过的细胞
                }//本方向搜索到细胞就入队
            }
        }while(t<w);//直至队空为止
    }
    
    //主函数
    int main(){
        //初始化数据
        int i,j;
        char s[100],ch;
        scanf("%d%d\n",&m,&n);
        for (i = 0; i <=m-1 ; ++i) {//将二维数组初始化
            for (j = 0; j <=n-1 ; ++j) {
                bz[i][j]=1;
            }
        }
        for (i = 0; i <=m-1 ; ++i) {//给二维数组赋初值
            gets(s);
            for (j = 0; j <=n-1 ; ++j) {
                if(s[j]=='0'){
                    bz[i][j]=0;
                }
            }
        }
    
        //调用BFS处理数据
        for (i = 0; i <m; ++i) {
            for (j = 0; j <n ; ++j) {
                if(bz[i][j]){
                    doit(i,j);
                }
            }
        }
    
        //输出数据
        printf("NUMBER of cells=%d",num);
    
        return 0;
    }

总结：

这个和上一篇文章类似，不过更复杂一点，这个需要用到纵横坐标来确定位置。比较困难的一部分还是广度优先算法doit的实现，其实只要按着图表分析也是比较容易理解的。开始我在电脑上做，虽然颜色可以多选，但是鼠标使用着不是很方便（出现错误），所以转而手工分析（正确解析），这里贴一下自己的计算过程

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FldzIwMTc_size_16_color_FFFFFF_t_70][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FldzIwMTc_size_16_color_FFFFFF_t_70 1][]

最后记录一下自己做题过程中出现的错误：

1.reference to 'map' is ambiguous|

c++编译出现此错误    表明定义的变量名字map和库函数map冲突而产生歧义，是因为自己引用了<bits/stdc++.h>

2.Process finished with exit code -1073741819 (0xC0000005)

这个具体的原因不清楚，但是后面我在检查的时候发现自己的二维数组写错了，也就是判断下一个是否是细胞那里写错了，所以输入样例数据后一直运行不出结果。后面修改好就可以运行了。可能是因为代码中间有语法错误或语义错误就会报这个问题。

3.是一个警告：Clang-Tidy: 'scanf' used to convert a string to an integer value, but function will not report conve

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FldzIwMTc_size_16_color_FFFFFF_t_70 2][]

这个问题不影响运行结果，但是有点奇怪，之前学习的时候都是使用cin或者scanf接受输入的数据，不知道为什么现在会有这种警告。网上搜了好像也没看懂。

4.学到了一个新知识——scanf“%1d”读入。

例如：scanf("%1d",&a\[i\]\[j\])

但是这个东西效率不搞，可以作为了解，写算法题的时候会拖延较长时间

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FldzIwMTc_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200216135100678.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FldzIwMTc=,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FldzIwMTc_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20200216135619161.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FldzIwMTc=,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FldzIwMTc_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20200216140713273.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FldzIwMTc=,size_16,color_FFFFFF,t_70