一本通1329细胞（使用广度优先搜索）

1329细胞
【题目描述】
一矩形阵列由数字00到99组成,数字11到99代表细胞,细胞的定义为沿细胞数字上下左右还是细胞数字则为同一细胞,求给定矩形阵列的细胞个数。如:
阵列
4 10
0234500067
1034560500
2045600671
0000000089
有44个细胞。

【输入】
第一行为矩阵的行nn和列mm;
下面为一个n×mn×m的矩阵。
【输出】
细胞个数。
【输入样例】
4 10
0234500067
1034560500
2045600671
0000000089
【输出样例】
4

解题思路：
本题可以使用广度优先搜索，用一个队列来记录每次找到的一个完整的大cell。每一个大cell就调用一次搜索函数。
注意几个问题：
1、可以用dx,dy数组记录上下左右
2、广度优先搜索中t是队列的头部，w是队列的尾，每次t所指向的都是当前的“父亲”。而后要寻找这一父亲数据的上下左右有哪些可以拉过来做其“儿子”的，对儿子进行入队，入队就要w++。
3、只有按顺序选出来的入队的才进行编号，编号从1开始。
4、需要一个二维数组h，来记录队列中各个编号所对应的数据。比如：h[1][0]表示队列中编号为1的那个数据在原始方格中的横坐标。h[1][1]表示队列中编号为1的那个数据在原始方格中的纵坐标。
5、b数组用来记录检查哪些方格是否可以入队，对于已经入队过一次的，需要将其置为0，表示不可以再入队了。
6、t++表示下一个相对的父亲，从而会寻找“新父亲”的儿子。（t是横向移动）

结合例子：
0234500067
1034560500
2045600671
0000000089

#include<iostream>
#include<string.h>
#include<stdio.h>
using namespace std;
//建立一个记录数组，1~9表示有小cell，0表示没有小cell
int b[102][102]; 

//用两个数组存上下左右 
int dx[]={1,-1,0,0};
int dy[]={0,0,-1,1};

//设队头和队尾  还有记录的结果num数 
int t,w=0;
int num=0;

//开始寻找，广度优先，找上下左右，用队列  一个完整的细胞就调用一次函数
int doit(int x, int y)//调用这个函数的时候说明已经找到一个小cell了，需要完成整个大cell的归纳 
{
 num++;
 t=0;
 w=1;//对头和尾初始化
 int h[10000][2];//专门用来记录数值的，在这里表示，当前入队编了号的数据是哪一个单元格 
 memset(h,0,sizeof(h));//对h数组进行初始化 
 b[x][y]=0;//表示已经检查过了，不能再检查了 先对头入队 头是1号 
 h[1][0]=x; h[1][1]=y; 
 
 int xl,yl;//设立x,y用来记录当前正在检查的横纵坐标值 
 while(t<w)
 {
  t++;//移到这一次的父亲 
  for(int i=0;i<=3;i++)
  {
   xl=h[t][0]+dx[i];//找父节点的上下左右 
   yl=h[t][1]+dy[i];
   if(b[xl][yl]!=0)//因为周围包裹起来了，所以不用判断出界 
   {                    //如果符合条件 
    //入队 
    w++;//扩充编号 
    h[w][0]=xl;
    h[w][1]=yl;//记录新入队编号的数值 
    b[xl][yl]=0;//表示已经走过了 
   }
   }
 }
  
 return 0;
}

int main()
{
 int n,m;
 cin>>n>>m; 
 memset(b,0,sizeof(b));//对b数组初始化 
 char s;//建一个字符变量，用来读数，因为所有数字连在一起，所以只能字符读入 
 for(int i = 1;i<=n;i++)
  for(int j=1;j<=m;j++)
  {
   cin>>s;
   b[i][j]=int(s-'0');
  }
 
 for(int i=1;i<=n;i++)//只有找到了一个小cell才会去查看这整个大cell 
  for(int j=1;j<=m;j++)
  {
   if(b[i][j]!=0)
    doit(i,j);
   } 
 
 cout<<num;
 return 0;
}