四色算法

Question

每幅地图都可以用四种颜色着色，使得有共同边界的国家着上不同的颜色。各位谁有什么好的算法

Answer 1

各位DX能不能给个例子，看C的代码头昏的厉害……

Answer 2

说实话这也是在网上找的，BOSS让我自己写，我很困惑* 算法介绍：
1。顺序查找属于国家n的点，找到后用临时数组cmap[][]存储该点坐标，并用IsFind = true表示已经找到。
如果IsFind = true，且某一行未出现属于国家n的点，说明属于国家n的点已经全部找到（ 因为每个国家的领土都是连续的）
，结束查找。
2。遍历cmap[][]，判断n与哪些国家相邻，把相邻的国家记录到临时数组record[n]（只要记录比n小的国家就好）
使得record[i] = -color[i]。
3。根据record[i]，判断color[n]。
*/ void SetColor(const int Map[100][100], const int MapSize, const int nCountries, int Color[])
{
      Color[0] = 1; //先确定第1个国家的颜色
      int cMap[10000][2] = {0};//用来存储所要处理的国家领土在地图上的坐标，cMap[][0]表示横坐标，cMap[][1]表示纵坐标      for (int country=1; country<nCountries; country++)//从第2个国家开始，处理每一个国家
      {
            int *record = new int[nCountries];//用来记录与country相邻的国家，
            //若i国与country国相邻，则record[i] = -color[i]，不相邻则默认为record[i] = 0;
            for (int i=0; i<nCountries; i++)
                  record[i] = 0;            int top = 0; //用来存储country国的领土个数，即在地图中所占的点数
            if ((top = Find(Map, cMap, MapSize, country+1)) != 0)//查找country国的国家领土在地图上的坐标，并返回领土个数
            {
                  for (int i=0; i<top; i++)//记录与country相邻的国家
                  {
                        int x = cMap[i][0], y = cMap[i][1];//x表示横坐标，y表示纵坐标                        if (y > 0 && Map[x][y-1] > 0 && Map[x][y] > Map[x][y-1])
                              record[Map[x][y-1]-1] = -Color[Map[x][y-1]-1];
                        if (y < MapSize-1 && Map[x][y+1] > 0 && Map[x][y] > Map[x][y+1])
                              record[Map[x][y+1]-1] = -Color[Map[x][y+1]-1];
                        if (x > 0 && Map[x-1][y] > 0 && Map[x][y] > Map[x-1][y])
                              record[Map[x-1][y]-1] = -Color[Map[x-1][y]-1];
                        if (x < MapSize-1 && Map[x+1][y] > 0 && Map[x][y] > Map[x+1][y])
                              record[Map[x+1][y]-1] = -Color[Map[x+1][y]-1];
                  }                  if (!SaveColor(record, Color, country))//根据record[i]，判断color[n]。
                  {
                        cout << "四色定理不成立！" << endl;
                        exit(1);//若
                  }
            }
            delete []record;
      }
}
//根据record[i]，判断color[n]。
bool SaveColor(const int record[], int Color[], int country)
{
      int i, j;
      for (i=1; i<=4; i++)
      {
            for (j=0; j<country; j++)
            {
                  if (i + record[j] == 0)
                        break;
            }
            if (j == country)
            {
                  Color[country] = i;
                  return true;
            }
      }
      return false;
}
//查找country国的领土在地图上的坐标，并返回领土个数
int Find(const int Map[][100], int cMap[][2], int MapSize, int country)
{
      bool IsFind = false;
      int top = 0;
      for (int i=0; i<MapSize; i++)
      {
            for (int j=0; j<MapSize; j++)
            {
                  if (Map[i][j] == country)
                  {
                        IsFind = true;
                        cMap[top][0] = i;
                        cMap[top][1] = j;
                        top++;
                  }
            }
            if (IsFind && Nothing(Map, MapSize, i, country))
                  break;
      }
      return top;
}
//判断第row行是否存在country国的领土，不存在返回真，否则返回假
bool Nothing(const int Map[][100], int MapSize, int row, int country)
{
      for (int j=0; j<MapSize; j++)
      {
            if (Map[row][j] == country)
                  return false;
      }
      return true;
}