• 1
  • 2
  • 3
  • 4
  • 5
  • 6

用栈实现四种颜色对地图的染色

数学上有个四色原理,对一个地图而言,可以用四种颜色将地图染色而且相邻两个国家颜色不同,下面使用C语言实现对一个简单地图的染色。代码如下:


#include 
 
char map[7][7]={-1,1,1,1,1,1,0,
                1,-1,0,0,0,1,0,
                1,0,-1,1,1,0,1,
                1,0,1,-1,1,0,0,
                1,0,1,1,-1,1,0,
                1,1,0,0,1,-1,0,
                0,0,0,0,0,0,-1,
               };                   //初始化地图,map[i][j]=1表示第i+1,和j+1块相连,0表示不相连,-1表示无意义
 
typedef struct _stack
{
    int i;
    char a[7];
}stack;
/*实现用4种颜色染色,要求相邻的块不同用同种颜色,下面 1 表示紫色 2表示黄色
  3表示红色,4表示绿色,每个区域按照上面四种颜色的顺序进行染色,先暂定第一块的
  颜色为 1 ,对于后面,先寻找一个与前面相邻块不同的颜色,入栈,如果没找到,将栈顶
  颜色出栈,如果前面已经是 4 颜色,继续退栈,否则当前颜色值上调,压入栈
  由于和前面相邻节点比较是会破坏栈的封装性,所以没写出它的操作,下面只是模拟了栈先进后出的性质而已而已*/
void dye()
{
    stack s;
    int i=0,j,k,cur,t;
    char color,flag,flag_2=0;    //flag_2检测前面是否退栈,即是否向前回溯
    s.i=-1;
    s.i+=1;
    s.a[i]=1;
    while(i<7)
    {
        t=1;
		if(flag_2)   //如果发生退栈,这样原来不是栈顶元素成为栈顶,颜色值增加
        {
        	t=s.a[i]+1;
        }
		for(j=t;j<=4;j++)
        {
            flag=1;
            for(k=0;k<=i;k++) { if(map[i+1][k]==1&&j==s.a[k]) //相邻而且j颜色已经在与其相邻的块的被使用 { flag=0; break; } } if(flag) //找到合适的颜色与相邻快颜色都不相同,将该颜色入栈 { color=j; s.i+=1; i=s.i; s.a[i]=color; break; } } flag_2=0; if(j>4)   //没有找到合适的颜色,退栈
        {
            s.i-=1;
            i=s.i;
            flag_2=1;
            while(s.a[i]==4)  //前面的一个块也已经4种颜色都尝试,继续退栈
            {
                s.i-=1;
                i=s.i;
            }
            if(i==-1)   //如果栈空,表示找不到一种涂色方案
            {
                printf("can't find any solution!\n");
                return ;
            }
        }
    }
    for(j=0;j<7;j++)
    {
        char ch=s.a[j];
        printf("%d:",j+1);
        switch(ch)
        {
        case 1:
        {
            printf("purple\n");
            break;
        }
        case 2:
        {
            printf("yellow\n");
            break;
        }
        case 3:
        {
            printf("red\n");
            break;
        }
        case 4:
        {
            printf("green\n");
            break;
        }
        }
    }
}
 
int main()
{
	dye();
	return 0;
}

转载

https://blog.csdn.net/mskeheng/article/details/21467771?utm_medium=distribute.pc_relevant.none-task-blog-BlogCommendFromMachineLearnPai2-5.compare&depth_1-utm_source=distribute.pc_relevant.none-task-blog-BlogCommendFromMachineLearnPai2-5.compare

 

点赞

发表评论

电子邮件地址不会被公开。必填项已用 * 标注