ranse.cpp

VC++实现染色算法

// ranse.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include "stdio.h"
#define N 20
typedef struct
{
	int arr[N][N];
}Tu;
void mapcolor(Tu R,int n,int s[])
{
	s[1] = 1;                                            // 1号区域染1色
    int a = 2,J = 1,k = 0;                                     // a为区域号，J为染色号
    while (a <= n)
    { 
		while(( J <=4 )&&(a <= n))  
         { 
			k = 1;                                     // k表示已经着色的区域号
			while((k < a)&&(s[ k ] * R.arr[a-1][k-1] != J))       
				k = k + 1;  // 若不相邻，或若相邻且不重色，对下一个区域判断。
			if (k < a)  
				J = J + 1;             //相邻且重色
			else
			{ 
				s[a] = J;  
				a = a + 1; 
				J = 1; 
			}       //相邻且不重色
		}
       if (J > 4)
	   {  
		   a = a - 1; 
		   J = s[a] + 1; 
	   }
	}
}

int main(int argc, char* argv[])
{
    Tu T1;
	int s1[N] = {0};
	int n1 = 0,i = 0,j = 0,l1 = 0,r1 = 0;
	printf("\n请输入地图包含区域个数num:\n");
	scanf("%d",&n1);
	for(i = 0;i < n1;i++)
		for(j = 0;j < n1;j++)
		{
			T1.arr[i][j] = 0;
		}
	printf("\n地图情况:\n");
	printf("请输入相联区域标号:(i(1..num),j(1..num);输入0,0表示结束)\n");
	scanf("%d,%d",&l1,&r1);
	while(l1 != 0 || r1 != 0)
	{
		if(l1 > n1 || r1 > n1 || l1 == 0 || r1 == 0)
		{
			printf("输入错误!请重新输入!\n");
			scanf("%d,%d",&l1,&r1);
		}
		else
			T1.arr[l1 - 1][r1 - 1] = T1.arr[r1 - 1][l1 - 1] = 1;
		scanf("%d,%d",&l1,&r1);
	}
    mapcolor(T1,n1,s1);
	printf("染色情况为:");
	for(i = 1;i <= n1;i++)
		printf("%4d",s1[i]);
	printf("\n");
	return 0;
}