记一次广度优先搜索

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

输入

第一行输入两个整数，分别代表矩阵的行和列 输入m*n的矩阵，由数字0到9组成。

输出

细胞个数。

样例输入

4 10 
1 2 3 4 5 1 1 1 6 7 
1 0 3 4 5 6 1 5 1 0 
2 0 4 5 6 6 1 6 7 1
0 0 6 0 6 6 1 0 8 9

样例输出

1

BFS，属于一种盲目搜寻法，目的是系统地展开并检查图中的所有节点，以找寻结果。换句话说，它并不考虑结果的可能位置，彻底地搜索整张图，直到找到结果为止。
思路：从第一个点开始依次依次遍历它的相邻结点。将其四个方向上不为0的数置为0，直到第一个数的相邻及相邻的相邻。。。。全都为0后。在继续寻找下一个不为0的位置。又继续置为0的操作。

#include <stdio.h>

int s[50][50],ans = 0,m,n;              //s为图的大小。ans为细胞个数。m,n分别为行和列。
int x1[5] = {0,1,0,-1,0},y1[5] = {0,0,1,0,-1};        //模拟点行进的路线

int change(int x,int y)
{
    for (int i = 1;i <= 4;i ++)                   //向四个方向前进
    {
        if (x + x1[i] > 0 && x + x1[i] <= m && y + y1[i] > 0 && y + y1[i] > 0 && y + y1[i] <= n && s[x+x1[i]][y+y1[i]] != 0)
        //判断前进的方向是否越界以及前进的方向的点是否为0
        {
            s[x + x1[i]][y + y1[i]] = 0;        //该点不为0的情况下，将该点置为0
            change(x + x1[i],y + y1[i]);    //以该点为搜索基准，进行递归，进行下一次的四个方向的遍历。
        }
    }
}
int main()
{
    scanf("%d %d",&m,&n);
    for (int i = 1;i <= m;i ++)
        for (int j = 1;j <= n;j ++)
        {
            scanf("%d",&s[i][j]);
        }
    for (int i = 1;i <= m;i ++)
        for (int j = 1;j <= n;j ++)        //该处的i，j目的是为了将图所有的点走一遍
        {
            if (s[i][j] != 0)
            {
                s[i][j] = 0;      //将该点置为0，在资料查询中，有的资料要求必须置为0.但我想了哈，觉得并没有必要=_+
                change(i,j);
                ans ++;
            }
        }
        printf("%d",ans);
    return 0;
}