Se necesita con urgencia el programa fuente del problema de coloración de mapas en lenguaje C (diseño y análisis de algoritmos)

Comienza desde una provincia, píntala con cualquier color 1, recorre las provincias al lado de ella y píntala con un color diferente a las provincias que ya están pintadas y adyacentes a ella.

En teoría, 4 colores son suficientes. ¿Qué pasa con el problema de los cuatro colores del mapa?

Puede haber múltiples soluciones. Todas las soluciones se pueden generar mediante recursividad (dfs).

Código fuente del lenguaje C del algoritmo de coloración de mapas

Anteriormente escribí un código fuente en C para colorear mapas (es decir, el principio de los cuatro colores).

Después de terminar de escribirlo, lo pensé y sentí que aún no era perfecto, porque desde un punto de vista práctico, los cuatro colores disponibles están colocados uno al lado del otro, y diferentes personas pueden tener Diferentes órdenes de selección. Además, diferentes personas podían elegir diferentes ciudades como puntos de partida para colorear, y el programa en ese momento no lo tenía en cuenta.

Entonces, modifiqué el programa para que se pareciera a lo siguiente y pedí a mis colegas que analizaran y señalaran las deficiencias en el código:

#i nclude stdio.hgt;

#; define N 21

int allcolor[4];/*Colores disponibles*/

int ok(int metro[N][N], int r_color[N], int current)

{/*La función ok y la siguiente función go son las mismas que las originales, reservadas para comparar los dos algoritmos*/

int j;

for(j= 1;jlt;current;j)

if(metro[current][j]==1amp;amp;r_color[j]==r_color[current])

devolver 0 ;

devolver 1;

}

void go(int metro[N][N], int r_color[N], int suma, int actual)

{

int i

if(currentlt;=sum)

for(i=1; ilt;=4; i )

{

r_color[actual]=i;

if(ok(metro, r_color, actual))

{

ir(metro, r_color, suma, corriente 1

retorno

}

}

}

color vacío(int metro[N][N], int r_color[N], int suma, int inicio)

{

int i , j, k;

r_color[inicio]=allcolor[0];

for(i=inicio 1; i!=inicio; i=(i 1)(suma 1 ))/*Considere todos los números como un anillo*/

if(i==0)/*Los números de ciudades comienzan desde 1, por lo que se omite el número 0*/

continuar;

más

for(j=0;jlt;4;j)

{

r_color[i ]=allcolor [j];/*Seleccione el siguiente color y los resultados serán diferentes según el orden de los colores en allcolor*/

for(k=1;klt;i;k)/* Verifique si hay algún conflicto y sienta que también se puede mejorar, como usar el método de búsqueda tabú*/

if(metro[i][k]==1amp;amp;r_color[k]= =r_color[i])

romper

if(kgt; =i)

romper

}

}

void main()

{

int r_colo

r[N]={0};

int t_color[N]={0};

int i

int inicio /* punto*/

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; /*Orden de selección de colores, orden diferente, resultados diferentes*/

start=1;

/* clrscr();*/

printf("\nTodo el color es:\n");

for(i= 0; ilt; 4; i )/*Orden de selección de color actual*/

printf("d ", allcolor[i]);

go(metro, r_color, 20, 1);

printf("\nPrimer método:\n");

for(i=1;ilt;=20;i)

printf ("3d", r_color[i]);

color(metro, t_color, 20, inicio

printf("\nSegundo método:\n"); p> p>

printf("\nY el metro de inicio es: d\n", start);

for(i=1;ilt;=20;i)

printf("3d", t_color[i]);

}

Aunque se dice que es coloración humanizada, en realidad hay otra cuestión que no se ha considerado, que es decir, el operador salta para colorear. Al igual que todos juegan el juego "Buscaminas". De hecho, también es fácil de implementar. Puede definir el orden de color tal como define el orden de selección de color.