Pers.narod.ru. Алгоритмы. Раскраска карты или матрица смежности

Страны на карте заданы матрицей смежности. Если страны i,j имеют на карте общую границу, то элемент матрицы A[i,j] равен 1, иначе 0. Смежные страны не должны иметь одинакового цвета. "Раскрасить" карту минимальным количеством цветов.

По сути дела, перед нами известная "задача о четырёх красках", доказывающая, что любую плоскую карту с произвольными границами областей можно раскрасить не более, чем четырьмя цветами. Если исключить всю интерфейсную работу, решение сведется к следующему коду обработки матрицы смежности A:

 a[0][0]=1;
 mc=2; //max color
 Print (); //Метод для вызова печати матрицы

 for (i=1; i<n; i++) {
  for (k=1; k<mc; k++) {
   for (j=0; j<i; j++) {
    if ((j!=i) && (a[i][j]==1) && (a[j][j]==k)) goto next_k;
   }
   a[i][i]=k;
   goto next_i;
next_k:
  }
  if (a[i][i]==0) {
   a[i][i]=mc;
   mc++;
  }
next_i:
  Print ();
 }

 Архив ZIP с файлами (16 Кб, запускать !start.bat, передающий программе файл данных с матрицей смежности)

Рейтинг@Mail.ru

вверх гостевая; E-mail
Hosted by uCoz