/*多叉路口交通灯系统设计思路分析：
1。假设存在N个路口，在这N个路口的交叉处设立一个交叉路口及交通灯；并且车辆指定从某方向到某方向行驶；
2。先用贪心算法将N个路口分组；
3。然后，用地图着色算法对分在同一组的路口上色；*/

！！现在主要的问题是：2－6个路口都可以具体设计一个矩阵去表示他们路线的关系；但是，若是N个路口，应该怎样构造矩阵？

#include <stdio.h>
/*"1"means the same color,"0" means different color.*/
int allcolor[4];/*可用的颜色*/
#define N 13
void color(int metro[N][N],int r_color[N],int sum)
{
   int i,j,k;
   for(i=1;i<=sum;i++)/*检查所有路口交通情况*/
     for(j=1;j<=4;j++)/*对每个路口尝试4种颜色的着色方案*/
     {
        r_color[i]=j;/*尝试着色*/
        for(k=1;k<i;k++)/*检查是否与相邻路口颜色相同*/
            if(metro[i][k]==1&&r_color[k]==r_color[i])
               break;/*相同则跳出，此时有k<i，则下面条件不成立，继续尝试下一种颜色*/
        if(k>=i)/*若不相同，则使用当前颜色，并检查下一个路口*/
            break;
     }
}

void main()
{
   int r_color[N]={0};
   int t_color[N]={0};
   int i;
   int start;/*着色的起点*/
   int metro[N][N]={{1,0,0,0,1,1,1,1,0,1,1,1,0},
                    {0,1,0,0,1,1,1,1,0,1,1,1,0},
                    {0,0,1,0,1,1,1,1,0,1,1,1,0},
                    {0,0,0,1,1,1,1,1,0,1,1,1,0},
                    {1,1,1,1,1,0,1,1,1,0,1,1,1},
                    {1,1,1,1,0,1,1,1,1,0,1,1,1},
                    {1,1,1,1,1,1,1,0,1,1,1,1,1},
                    {1,1,1,1,1,1,0,1,1,1,1,1,1},
                    {0,0,0,0,1,1,1,1,1,1,1,1,0},
                    {1,1,1,1,0,0,1,1,1,1,1,1,1},
                    {1,1,1,1,1,1,1,1,1,1,1,0,1},
                    {1,1,1,1,1,1,1,1,1,1,0,1,1},
                    {0,0,0,0,1,1,1,1,0,1,1,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]);
   color(metro,t_color,12);
   printf("\nAnd the start metro is:%d\n",start);
   for(i=1;i<=13;i++)
     printf("%3d",t_color[i]);
   getch();
}

[em1]