问题描述：
    为了增强幼儿园小朋友的数数能力，小虎的老师给了一个家庭游戏作业。让小虎拿一块空的围棋盘，随机在一些方格中放些棋子(有黑白两种颜色)，如果一个方格和它的上、下、左、右四个方格之一都有相同颜色的棋子，则认为两格子是相连通的。这期间，要求小虎不断统计共有多少个连通块。
    如下图是一个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 编辑 ]

floodfill嘛

floodfill用扫描线法快，不过比BFS难写一点

能用BFS吗？

基本算法有了，下来要具体问题具体分析，就能解决问题了！！
-------------------------------------------------------------------
这个题目按照要求，规模比较小呢！最大19*19就足够了啊！！

[ 本帖最后由 jack10141 于 2010-9-13 16:25 编辑 ]

我想可以对每个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为查找棋子有几个连通块
}

今天有空，写了个简单的实现代码，楼主参考下，（我用递归实现，相对容易理解，但是，如果规模太大，我担心程序会崩溃），也顺便请帮忙测试下

#include <stdio.h>
#include <stdlib.h>

#define MAXL 20              //定义了block棋盘二维数组的最大值为20*20的矩阵
int n,m;                     //n为用户定义数组的大小(n<=19)，m为共放了几个棋子(m<=361)
int block[MAXL][MAXL];       //block为棋盘，
int color[MAXL][MAXL]={0};   //color为染色棋盘，颜色编号1~m,0表示无棋子，不染色
int Color;                   //Color 当前颜色
int testcolor(int x,int y,int b)  //测试该点是否可以填充当前颜色,b为起点棋子黑或白（0 or 1）
{
    if(x<1 || x>n)           //x坐标出界
        return 0;
    if(y<1 || y>n)           //y坐标出界
        return 0;
    if(color[x][y])          //该点已被染色
        return 0;
    if(block[x][y] == b)     //当前点与起点棋子色彩是否一致 
        return 1;            //一致，则可以填充当前颜色
    else
        return 0;            //不一致，则不可以填充当前颜色
}
int floodfill(int x,int y)   //从起点x,y开始填充连通区域
{
    color[x][y]=Color;
    if(testcolor(x-1,y,block[x][y]))   //向上填充
    {
        floodfill(x-1,y);
    }
    if(testcolor(x+1,y,block[x][y]))   //向下填充
    {
        floodfill(x+1,y);
    }
    if(testcolor(x,y-1,block[x][y]))   //向左填充
    {
        floodfill(x,y-1);
    }
    if(testcolor(x,y+1,block[x][y]))   //向右填充
    {
        floodfill(x,y+1);
    }
    return 0;
}
int test_NUM_of_color()                //测试当前连通块数目并输出结果
{
    int i,j,b,x,y;                     //i,j为循环用,x,y为棋子坐标，b为颜色
    Color=0;
    for(i=1;i<=n;i++)
        for(j=1;j<=n;j++)
            color[i][j]=0;
    for(i=1;i<=n;i++)
        for(j=1;j<=n;j++)
            if(block[i][j] != -1 && !color[i][j]) //如果当前位置有棋子，并且未填颜色
            {
                Color++;               //颜色加1
                floodfill(i,j);        //填充连同区域
/*
for(x=1;x<=n;x++)                       //显示当前棋盘
{
    for(y=1;y<=n;y++)
        printf("%3d",block[x][y]);
    printf("\n");           
}
system("pause");
for(x=1;x<=n;x++)                       //显示当前颜色表
{
    for(y=1;y<=n;y++)
        printf("%3d",color[x][y]);
    printf("\n");           
}
system("pause");
*/
            }
    printf("\n当前连通块数为%d\n",Color);
}

int main()
{
    int i,j,b,x,y;                     //i,j为循环用,x,y为棋子坐标，b为颜色
    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<m;i++)
    {   
        scanf("%d%d%d",&b,&x,&y);      //输入棋子的颜色b，坐标x,y
        block[x][y]=b;                   //存入棋盘
        test_NUM_of_color();           //测试当前连通块数目并输出结果
    }
}

 

[ 本帖最后由 jack10141 于 2010-9-14 13:24 编辑 ]

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