问题描述：
    为了增强幼儿园小朋友的数数能力，小虎的老师给了一个家庭游戏作业。让小虎拿一块空的围棋盘，随机在一些方格中放些棋子(有黑白两种颜色)，如果一个方格和它的上、下、左、右四个方格之一都有相同颜色的棋子，则认为两格子是相连通的。这期间，要求小虎不断统计共有多少个连通块。
    如下图是一个59的一块棋盘，其中“.”表示空格，“*”表示黑棋子，“@”表示白棋子。则有4块连通的棋子块。
       .........
       ..**..@..
       .**@@.@@.
       ..*@..*..
       .........
    哥哥大虎在一边看一边想，如果棋盘是nn的，共放了m个棋子，如何用计算机解决这个问题呢?
   
输入格式：
    第1行有2个整数n,m，
    下面m行，每行三个整数：C(0C1)，X,Y(1X,Yn)。分别表示依次放入棋子的颜色(0表示白色，1表示黑色)，要放入格子的横坐标和格子的纵坐标。
输入一：                                    
3 5         
1 1 1
1 1 2
0 2 2
1 3 1
1 2 1

输出格式：
    共m行。第i行一个整数，表示放入第i个棋子后，当前有多少个棋子连通块。
输出一：
1
1
2
3
2






输入二：
3 5
1 1 2
1 2 1
1 3 2
1 2 3
1 2 2
输出二：
1
2
3
4
1



我的思路是这样的，先定义一个100*100的二维数组，将白棋赋予1值，将黑棋赋予0值，然后将其他的空格赋予-1值。各位是怎么想的呢？给个思路，大家一起探讨！

先打了一个框架，大家看看：
#include <stdio.h>
#define MAXL 100//定义了block二维数组的最大值为100*100的矩阵
void put_pieces(int x[MAXL],int y[MAXL],int block[MAXL][MAXL],int pieces[MAXL],int m)//摆放棋子
{
    int i,j;
    for(i=0;i<m;i++)
    block[x[i]][y[i]]=pieces[i];//将棋子的值赋给棋盘
}
void main()
{
    int x[MAXL],y[MAXL],block[MAXL][MAXL],pieces[MAXL],i,j,n,m;//block为棋盘，i,j为循环用,x,y为坐标。
    scanf("%d %d",&n,&m);//n为用户定义数组的大小，m为共放了几个棋子
    for(i=0;i<n;i++)
    for(j=0;j<n;j++)
    block[i][j]=-1;//将棋盘全部赋给-1值，因为0是白棋，1是黑棋
    for(i=0;i<n;i++)
    scanf("%d %d %d %d",pieces[i],x[i],y[i]);//输入棋子的颜色，坐标
    put_pieces(x,y,block,pieces,n,m);//将坐标，棋盘，颜色,基本信息，传入摆放棋子函数中
}


[ 本帖最后由 sunyh1999 于 2010-9-12 17:19 编辑 ]

能用BFS吗？

我想可以对每个pieces都判断一下，各位有什么想法

大致的框架我勾出来了：
#include <stdio.h>
#define MAXL 20//定义了block二维数组的最大值为100*100的矩阵
void search_pieces(int x[MAXL],int y[MAXL],int block[MAXL][MAXL],int pieces[MAXL],int m,int n)//查找连通块
{
   
}
void put_pieces(int x[MAXL],int y[MAXL],int block[MAXL][MAXL],int pieces[MAXL],int m)//摆放棋子
{
    int i;
    for(i=0;i<m;i++)
    block[x[i]][y[i]]=pieces[i];//将棋子的值赋给棋盘
}
void main()
{
    int x[MAXL],y[MAXL],block[MAXL][MAXL],pieces[MAXL],i,j,n,m;//block为棋盘，i,j为循环用,x,y为坐标。
    scanf("%d %d",&n,&m);//n为用户定义数组的大小，m为共放了几个棋子
    for(i=0;i<n;i++)
    for(j=0;j<n;j++)
    block[i][j]=-1;//将棋盘全部赋给-1值，因为0是白棋，1是黑棋
    for(i=0;i<n;i++)
    scanf("%d %d %d %d",pieces[i],x[i],y[i]);//输入棋子的颜色，坐标
    put_pieces(x,y,block,pieces,m);//将坐标，棋盘，颜色,基本信息，传入摆放棋子函数中
    search_pieces(x,y,block,pieces,m,n);//search_pieces为查找棋子有几个连通块
}

没看懂为什么放第一个的连通块是1

可是题目要求的是上下左右之一有一个相同颜色的棋子。第一个棋子不可能连通块，可是输入输出要求上写一个连通块，这是怎么回事呢？

那么输出要求就不符合了。你能详细给我讲讲你的理解，也就是说你认为哪几个算连通块，写个示意图或是标出哪几个是连通块？

其实我的算法也是跟你一样的，先将棋子放入棋盘，然后枚举每一个棋子，将已经连通的棋子块在另一个数组里标记好，最后打印出count，就OK了

是的，用递归回溯做这道题确实不是很好，即使不奔溃也要超时，时间限制为1s。你可以用我现在正在写的框架试试：

#include <stdio.h>
#define MAXL 20//定义了block二维数组的最大值为20*20的矩阵
int blackcount=0,blackcounterd[MAXL][MAXL]={0};//blackcount为记录有几个连通块，blackcounter为标记
void search_pieces(int x[MAXL],int y[MAXL],int block[MAXL][MAXL],int pieces[MAXL],int m,int n)//查找连通块
{
    int i,j;
    for(i=0;i<n;i++)
    for(j=0;j<n;j++)

}
void put_pieces(int x[MAXL],int y[MAXL],int block[MAXL][MAXL],int pieces[MAXL],int m)//摆放棋子
{
    int i;
    for(i=0;i<m;i++)
    block[x[i]][y[i]]=pieces[i];//将棋子的值赋给棋盘
}
void main()
{
    int x[MAXL],y[MAXL],block[MAXL][MAXL],pieces[MAXL],i,j,n,m;//block为棋盘，i,j为循环用,x,y为坐标。
    scanf("%d %d",&n,&m);//n为用户定义数组的大小，m为共放了几个棋子
    for(i=0;i<n;i++)
    for(j=0;j<n;j++)
    block[i][j]=-1;//将棋盘全部赋给-1值，因为0是白棋，1是黑棋
    for(i=0;i<n;i++)
    scanf("%d %d %d %d",&pieces[i],&x[i],&y[i]);//输入棋子的颜色，坐标
    put_pieces(x,y,block,pieces,m);//将坐标，棋盘，颜色,基本信息，传入摆放棋子函数中
    search_pieces(x,y,block,pieces,m,n);//search_pieces为查找棋子有几个连通块
}