用dfs 不行么?

也可以啊，最好使用foodfill或是BFS

哦 版主 能加 Q1585815624 么!
本人高中生还请赐教!

[ 本帖最后由 a351357741 于 2010-9-15 20:50 编辑 ]

#include <stdio.h>
#include <stdlib.h>
#define MAXL 20//定义了block二维数组的最大值为20*20的矩阵
int blackcount=0,blackcounterd[MAXL][MAXL]={0},count_b=0,n=0;//blackcount为记录有几个连通块，blackcounter为标记
void print()//打印结果
{
    printf("%d",blackcount);
}
void changecolor(int newcolor,int oldcolor)
{
    int i,j;
    for(i=0;i<n;i++)
    for(j=0;j<n;j++)
        if(blackcounterd[i][j]==oldcolor)blackcounterd[i][j]=newcolor;
}
void text_data(int x[MAXL],int y[MAXL],int pieces[MAXL],int m,int n)// 校验
{
    int i;
    for(i=0;i<n;i++)
    {
    if(x[i]<1||x[i]>n)
    {
        printf("Your input data is error!");
        getchar();
        exit(0);
    }
    if(y[i]<1||y[i]>n)
    {
        printf("Your input data is error!");
        getchar();
        exit(0);
    }
    if(pieces[i]!=0&&pieces[i]!=1)
    {
        printf("Your input data is error");
        getchar();
        exit(0);
    }
    }
}
void connected(int temp_x,int temp_y,int a,int b)
{
if(blackcounterd[temp_x][temp_y]==0)// //尚未染色的情况，与临块颜色相同
blackcounterd[temp_x][temp_y]=blackcounterd[a][b];
else if(blackcounterd[temp_x][temp_y]!=blackcounterd[a][b])
{
    changecolor(blackcounterd[temp_x][temp_y],blackcounterd[a][b]);
    count_b--;
}
}
void search_pieces(int x[MAXL],int y[MAXL],int block[MAXL][MAXL],int pieces[MAXL],int m,int n)//查找连通块
{
    int i,temp_x,temp_y;
    for(i=0;i<n;i++)
    {
       if(block[x[i+1]][y[i]]!=pieces[i]&&block[x[i-1]][y[i]]!=pieces[i]&&block[x[i]][y[i-1]]!=pieces[i]&&block[x[i]][y[i+1]]!=pieces[i])
        //如果这个棋子是孤立的就把色块加一
       {
           blackcount=blackcount+1;
           blackcounterd[x[i]][y[i]]=blackcount;//染色
           count_b++;
       }
       if(block[x[i-1]][y[i]]==pieces[i])//该棋子上连
       {
           temp_x=x[i];temp_y=y[i];//因为不能将数组存入整形变量所以用一个“替身”代替
           connected(temp_x,temp_y,temp_x-1,temp_y);
       }
       if(block[x[i+1]][y[i]]==pieces[i])//下连
       {
            temp_x=x[i];temp_y=y[i];//因为不能将数组存入整形变量所以用一个“替身”代替
           connected(temp_x,temp_y,temp_x+1,temp_y);
       }
       if(block[x[i]][y[i-1]]==pieces[i])//左连
       {
           temp_x=x[i];temp_y=y[i];//因为不能将数组存入整形变量所以用一个“替身”代替
           connected(temp_x,temp_y,temp_x,temp_y-1);
       }
       if(block[x[i]][y[i+1]]==pieces[i])//右连
       {
            temp_x=x[i];temp_y=y[i];//因为不能将数组存入整形变量所以用一个“替身”代替
           connected(temp_x,temp_y,temp_x,temp_y+1);
       }
    }
  
}
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,m;//block为棋盘，i,j为循环用,x,y为坐标。
    printf("please input n and m:\n");
    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是黑棋
    printf("棋盘初始化完毕!请输入数据:\n");
    for(i=0;i<m;i++)
    scanf("%d %d %d",&pieces[i],&x[i],&y[i]);//输入棋子的颜色，坐标
    text_data(x,y,pieces,m,n);//测试数据，将不正确的输入报错
    put_pieces(x,y,block,pieces,m);//将坐标，棋盘，颜色,基本信息，传入摆放棋子函数中
    search_pieces(x,y,block,pieces,m,n);//search_pieces为查找棋子有几个连通块
    print();//打印结果
}

jack10141在吗？帮我看看这段代码为何执行不下去：

  呵呵！！ 学习下。

呵呵,我在26楼不是又给了另外一种解决办法么?
那种办法才是这个问题的正解吧?
floodfill 虽然可以解决这个问题,但是规模大了后很难处理的!时间复杂度可能无法接受!
------------------------
你的代码,在什么地方出现问题?执行不下去的?
试着用加脚手架的办法,输出一些中间结果!查看哪里出问题啊!

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

看了看你34楼的代码,你的做法是将所有的棋子先顺次输入,存数组x y pieces
然后一次性全都写入棋盘(put_pieces 实现),但是这样的做法没办法求中间过程的连通块的啊!!只能求最后的块数量呢!
你再整理下思路??

我只要最后的连通块，你帮我看看我的代码有什么问题

汗 那我看看！！

你的代码其中有几处类似的问题：

       if(block[x[i-1]][y[i]]==pieces[i])//该棋子上连

应该是：
       if(block[x[i]-1][y[i]]==pieces[i])//该棋子上连


还有
       if(block[x[i+1]][y[i]]!=pieces[i]&&block[x[i-1]][y[i]]!=pieces[i]&&block[x[i]][y[i-1]]!=pieces[i]&&block[x[i]][y[i+1]]!=pieces[i])

另外就是你的两个变量 blackcount 和count_b 我感觉 有点混乱，
 
我的做法是染色时 颜色编号只增不减 但是 你借用我的处理方法，好像思路不对呢！
首先，我是棋子逐个放进去 逐个分析 所以 颜色数++或者不变，
当然新增棋子可能会将已有的原为两种颜色但是实际上是一种棋子的连为一个连通块，所以 要合并颜色 减少连通块数目
你处理的时候好像颜色编号还会减少啊！！你自己考虑下这个过程啊！！

如果像你所说的，只想得到最后的 连通块数目 那么 应该用 floodfill 方法，我的那个处理办法不适用呢！！

其他的地方还没细看，改正上面的所有4出问题后，要不你把思路你在整理下？？？

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