#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <ctype.h>

#define MAX_N 100 + 10 
#define MAX_STAR 160 + 10 
char source[MAX_N][MAX_N];
int  visit[MAX_N][MAX_N];
int w, h;
int dx[8] = {0,  0, 1, -1, 1,-1,  1,  -1 };
int dy[8] = {1, -1, 0,  0, 1, 1, -1, -1 };
typedef struct
{
		int num;
		long long det;
		int flag;
		int iSameNum;
}ST_cluster;

ST_cluster stCluster[30];

typedef struct
{
		int y;
		int x;
}ST_member;
ST_member stMember[MAX_STAR];
int iNum;
int iFlag;


void initVar()
{
		memset(source,  0, sizeof(source));
		memset((char *)&stCluster,  0, sizeof(stCluster));
		iFlag = 0;

}
void printfMatix()
{
		int i;
		for(i = 0; i<h; i++)
		{
				printf("%s\n", source[i]);
		}

}


void add(int y, int x)
{
		stMember[iNum].y = y;
		stMember[iNum].x = x;
		visit[y][x] = 1;
		iNum++;
}
void dfs(int y, int x)
{
		int i, yy, xx;
		for(i = 0; i<8; i++)
		{
				yy = y + dy[i];
				xx = x + dx[i];
				if(xx>=0 && xx<w && yy>=0 && yy<h && 0 == visit[yy][xx] && '1' == source[yy][xx])
				{
						
				//		printf("xx = %d, yy = %d,  visit[yy][xx] = %d, source[yy][xx] = %d\n", xx, yy, visit[yy][xx], source[yy][xx]);
						add(yy, xx);
						dfs(yy, xx);

				}
		}
}

void deal(int y, int x)
{

		int i, sumx = 0, sumy = 0;
		double ave_x = 0.0, ave_y = 0.0, det = 0.0, detTest = 0.0;
		long long detTemp;
		int iFlagFinal, iFound;
		double dTemp;
		iNum=0;
		add(y, x);
		dfs(y, x);

		for(i = 0; i<iNum; i++)
		{
				sumx += stMember[i].x;
				sumy += stMember[i].y;
		}
		ave_x = (double)sumx/iNum;
		ave_y = (double)sumy/iNum;
//		printf("sumx = %d, sumy = %d, ave_x = %f, ave_y = %f, iNum = %d\n", sumx, sumy, ave_x, ave_y, iNum);
		det = 0.0;
		for(i = 0; i<iNum; i++)
		{
				//det += (stMember[i].x - ave_x)* (stMember[i].x - ave_x)* (stMember[i].x - ave_x) + (stMember[i].y - ave_y)*(stMember[i].y - ave_y) *(stMember[i].y - ave_y);
				det += (stMember[i].x - ave_x)* (stMember[i].x - ave_x)* (stMember[i].x - ave_x)* (stMember[i].x - ave_x) + (stMember[i].y - ave_y) *(stMember[i].y - ave_y)*(stMember[i].y - ave_y) *(stMember[i].y - ave_y);
		}
		detTemp =(long long) (det *1000000);
//		if(400 == detTemp && iNum == 5)
//		{
//				for(i = 0; i<iNum; i++)
//				{
//						dTemp = ((double)stMember[i].x - ave_x)* ((double)stMember[i].x - ave_x) + ((double)stMember[i].y - ave_y) *((double)stMember[i].y - ave_y);
//						detTest += dTemp;
//						printf("stMember[i].x = %d, ave_x = %f, stMember[i].y = %d, ave_y = %f, dTemp = %f, detTest = %f\n", stMember[i].x, ave_x, stMember[i].y, ave_y, dTemp, detTest);
//				}
//
//		}
		//iFlag 有多少个相似的星系
		iFlagFinal = 0;
		iFound = 0;
		for(i = 0; i<iFlag; i++)
		{
				if(iNum == stCluster[i].num && detTemp == stCluster[i].det  )
				{
						iFlagFinal = stCluster[i].flag;
						stCluster[i].iSameNum++;
						iFound = 1;
						break;
				}
		}
		if(0 == iFound)
		{

				stCluster[iFlag].num = iNum;
				stCluster[iFlag].det = detTemp;
				stCluster[iFlag].flag = iFlag;
				stCluster[iFlag].iSameNum = 1;
				iFlagFinal = iFlag;
				iFlag++;
		}

		//printf("ave_x = %f,ave_y = %f det = %f, detTemp = %lld,iNum = %d,  iFlagFinal = %d, stCluster[iFlagFinal].iSameNum = %d \n", ave_x, ave_y,  det, detTemp, iNum, iFlagFinal, stCluster[iFlagFinal].iSameNum);
//		printf("iFlagFinal = %d, iFlag = %d\n", iFlagFinal, iFlag);
		for(i = 0; i<iNum; i++)
		{
				source[stMember[i].y][stMember[i].x] = 'a' + iFlagFinal;
		}
		//printfMatix();



}


int main()
{
		int i, j; 

		while(scanf("%d\n%d", &w, &h)!=EOF)
		{
				initVar();
//				printf("w = %d, h = %d\n", w, h);

//				printf("u = %d\n", 'u'-'a');
				for(i = 0; i<h; i++)
						scanf("%s", source[i]);

				//printfMatix();
				for(i = 0; i<h; i++)
				{
						for(j = 0; j<w; j++)
						{
								if( 0 == visit[i][j] && '1' == source[i][j] )
								{
										deal(i, j);
								}


						}
				}
			//	printf("after handle\n");
				printfMatix();

		}




}

• Re:判断连通分量是否一致。。。参照一个大神的。思路。但是不解为了啥。有人能探讨一下为啥么？ (112) 274856653 2019-09-26 22:09:10