dituzhuose 2.txt

来自「地图着色问题 任何平面地图可以使用4种颜色给每个不同的城市着色」· 文本 代码 · 共 97 行

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

#include "stdafx.h"

#include <stdio.h>
#define N 21
int allcolor[4];/*可用的颜色*/

int ok(int metro[N][N],int r_color[N],int current)
{/*ok函数和下面的go函数和原来的一样,保留用来比较两种算法*/
   int j;
   for(j=1;j<current;j++)
     if(metro[current][j]==1&&r_color[j]==r_color[current])
         return 0;
   return 1;
}

void go(int metro[N][N],int r_color[N],int sum,int current)
{
   int i;
   if(current<=sum)
      for(i=1;i<=4;i++)
      {
          r_color[current]=i;
          if(ok(metro,r_color,current))
          {
             go(metro,r_color,sum,current+1);
             return;
          }
      }
}

void color(int metro[N][N],int r_color[N],int sum,int start)
{
   int i,j,k;
   r_color[start]=allcolor[0];
   for(i=start+1;i!=start;i=(i+1)%(sum+1))/*把所有编号看作一个环*/
    if(i==0)/*城市号从1开始编号,故跳过0编号*/
       continue;
    else
     for(j=0;j<4;j++)
     {
        r_color[i]=allcolor[j];/*选取下一种颜色,根据allcolor中颜色顺序不同，结果不同*/
        for(k=1;k<i;k++)/*检查是否有冲突，感觉还可以改进，如使用禁忌搜索法*/
           if(metro[i][k]==1&&r_color[k]==r_color[i])
                break;
        if(k>=i)
                break;
     }
}

void main()
{
   int r_color[N]={0};
   int t_color[N]={0};
   int i;
   int start;/*着色的起点*/
   int metro[N][N]={{0},
                             {0,1,1,1,1,1,1},
                             {0,1,1,1,1},
                             {0,1,1,1,0,0,1},
                             {0,1,1,0,1,1},
                             {0,1,0,0,1,1,1,0,0,1,0,0,0,0,0,0,1},
                             {0,1,0,1,0,1,1,1,1,1},
                             {0,0,0,0,0,0,1,1,1},
                             {0,0,0,0,0,0,1,1,1,1,0,0,1},
                             {0,0,0,0,0,1,1,0,1,1,0,0,1,1,1,0,1},
                             {0,0,0,0,0,0,0,0,0,0,1,1,0,1,0,1,0,0,0,1},
                             {0,0,0,0,0,0,0,0,0,0,1,1,1,1,0,0,0,0,0,1},
                             {0,0,0,0,0,0,0,0,1,1,0,1,1,1,0,0,0,0,0,1,1},
                             {0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1},
                             {0,0,0,0,0,0,0,0,0,1,0,0,0,1,1,1,1},
                             {0,0,0,0,0,0,0,0,0,0,1,0,0,1,1,1,1,1,0,1},
                             {0,0,0,0,1,0,0,0,1,0,0,0,0,1,1,1,1},
                             {0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1},
                             {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1},
                             {0,0,0,0,0,0,0,0,0,0,1,1,1,0,0,1,0,0,1,1,1},
                             {0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,1,1}};
   allcolor[0]=1;allcolor[1]=2;allcolor[2]=3;allcolor[3]=4;/*选色顺序，顺序不同，结果不同*/
   start=1;
/*   clrscr();*/
   printf("\nAll color is:\n");
   for(i=0;i<4;i++)/*当前选色顺序*/
      printf("%d    ",allcolor[i]);
   go(metro,r_color,20,1);
   printf("\nFirst method:\n");
   for(i=1;i<=20;i++)
     printf("%3d",r_color[i]);
   color(metro,t_color,20,start);
   printf("\nSecond method:\n");
   printf("\nAnd the start metro is:%d\n",start);
   for(i=1;i<=20;i++)
     printf("%3d",t_color[i]);
}