求C语言地图四染色代码..
详细注解下...
2011-04-09 20:50
2011-04-09 23:22
程序代码：
#include<stdafx.h>
#include<stdlib.h>
#include<math.h>
#include<string.h>
#define INIT_STACK_SIZE 10
#define STACKINREMENT 5
typedef struct{
int * top;
int * base;
int stacksize;
}SqStack;
int checkMap(int , SqStack &, int );
void Push(SqStack &, int);
int Pop(SqStack &);
int MAP[20][20] ;
int locationNum ;
/*
int MAP[7][7] = {{0, 1, 1, 1, 1, 1, 0},
{1 ,0 ,0, 0, 0, 1, 0},
{1, 0, 0, 1, 1, 0, 0},
{1, 0, 1, 0, 1, 1, 0},
{1, 0, 1, 1, 0, 1, 0},
{1, 1, 0, 1, 1, 0, 0},
{0, 0, 0, 0, 0, 0, 0}};
*/
void PaintMap()
{
void GetMap();
SqStack stack;
stack.base = (int *)malloc(INIT_STACK_SIZE *sizeof(int));
stack.top = stack.base;
stack.stacksize = INIT_STACK_SIZE;
*stack.top++ = 1;
int color = 1; int section = 2;
int mark = 0;
GetMap() ; /*要求用户输入地图*/
while ( section<=locationNum)
{
while(( color <= 4)&&(section <= locationNum))
{
mark = checkMap(section, stack, color);
// 若不相邻，或若相邻且不重色，对下一个区域判断。
if (mark < section) color = color + 1; //相邻且重色
else
{
Push(stack, color); section = section + 1; color = 1;
}//相邻且不重色
}
if(color > 4)
{
section = section - 1; color = Pop(stack) + 1;
}
}
printf("染色的结果是 :\n" );
for(int i = 0; i < locationNum ; i++)
printf("%d ", *(stack.base + i));
printf("\n");
}
/*************************************************
要求用户输入地图的有关信息
*************************************************/
void GetMap(){
printf("需要染色的地区数 : ");
scanf("%d", &locationNum);
while(getchar() != '\n');
printf("输入地图 : \n");
for(int i = 0 ; i < locationNum ; i++)
{
char ch , lastCh ; int num = 0;
printf("与第 %d 号区域相邻的所有区域号 : " , i + 1);
while((ch = getchar()) != '\n')
{
if(ch == ' ' ){
MAP[i][num - 1] = 1 ;
num = 0;
}else
num = num * 10 + (ch - '0') ;
lastCh = ch ;
}
if(lastCh != ' ')
MAP[i][num - 1] = 1 ;
}
for(int j = 0; j < locationNum ; j++)
{
for(int k = 0; k < locationNum ; k++)
if(MAP[j][k] != 1)
MAP[j][k] = 0 ;
}
printf("输入的地图是 : \n");
for(int m = 0; m < locationNum ; m++){
for(int n = 0; n < locationNum ; n++)
printf("%d ", MAP[m][n]);
printf("\n");
}
}
/******************************************************
判断当前地区能否染当前的颜色
******************************************************/
int checkMap(int index, SqStack &stack, int color){
int mark = 1 ;
while((mark < index )&& (*(stack.base + mark - 1)) * MAP[mark-1][index-1] != color && color <= 4 )
mark++;
return mark;
}
void Push(SqStack &stack, int e)
{
if(stack.top-stack.base >= stack.stacksize){
stack.base = (int *)realloc(stack.base, (stack.stacksize + STACKINREMENT)*sizeof(int));
stack.top = stack.base + stack.stacksize;
stack.stacksize = stack.stacksize + STACKINREMENT;
}
*stack.top++ = e;
}
int Pop(SqStack &stack)
{
int e = 0;
if(stack.top - stack.base <= 0){
printf("ERROR !");
exit(1);
}
e = *--stack.top ;
return e;
}
int main()
{
PaintMap() ;
return 0 ;
}
2011-04-10 00:36
2011-04-10 00:37