mapcolour.cpp

地图染色问题

/*
 *地图染色
 */

#include<stdio.h>
#include<math.h>
#define MatrixSize 7

int matrix[MatrixSize][MatrixSize];

//读取文件

bool OpenFile(char *filename)
{
	FILE *fp;
	fp=fopen(filename, "r");

	if(!fp)
	{
		printf("文件无法打开！");
		return false;
	}

	for(int i=0;i<MatrixSize;i++)
	{
		for(int j=0;j<MatrixSize;j++)
		{
			fscanf(fp,"%d",&matrix[i][j]);
		}
	}
	fclose(fp);
	return true;
}

//染色

void  mapcolor(int R[MatrixSize][MatrixSize], int n, int *s)
{
	s[1]=1;         // 1号区域染1色
    int a=2,J=1;    // a:区域号,J:染色号
    while (a<=n)
    { 
	while((J<=4)&&(a<=n)) 
        { 
         int k=1;       // k表示已经着色的区域号
         while((k<a)&&(s[k]*R[a-1][k-1]!=J))  // 若不相邻，或若相邻且不重色，对下一个区域判断 
		   {
		       k=k+1; 
		   } 
           if (k<a)J=J+1;	//当从上一个循环跳出后，可判断若k<a相邻且重色
           else{s[a]=J;a=a+1;J=1;}//相邻且不重色
        };
       if (J>4) {a=a-1;J=s[a]+1;};  //J为染色号，J>4说明四色全部尝试后，不合适，a=a-1退一格尝试新颜色
    }
 }

//主函数

void main()
{
	int s[MatrixSize+1]={0};    //存放染色结果，0号单元不放
    int n=MatrixSize;

	char filename[16];
	printf("请输入文件名：");
	scanf("%s",filename);
	OpenFile(filename);

    mapcolor(matrix, n, s);
    for(int a=1; a<=n;a++)
	{
		printf("%d, ",s[a]);
	};
    printf("\n");
}