8. Colorarea unei hărţi

Desenul alăturat reprezintă o hartă cu 5 ţări

numerotate de la 1 la 5. Se generează toate variantele

de colorare a acestei hărţi având la dispoziţie 4

culori notate cu A, B, C, D, astfel încât oricare două

ţări vecine să nu fie colorate la fel. Prima soluţie este (A, B, C, A, B) având

următoarea semnificaţie: ţara 1 e colorată cu A,

ţara 2 e colorată cu B, ţara 3 e colorată cu C,

ţara 4 e colorată cu A, ţara 5 e colorată cu B.

Scrieţi un program care pentru o hartă dată să genereze toate variantele de colorare cu 4

culori a hărţii, astfel încât oricare două ţări vecine să nu fie colorate la fel.

Harta va fi reprezentată sub forma unei matrice a vecinilor, cu următoarea semnificaţie:

[ ] {

1 2 3 4 5 1 0 1 1 0 0 2 1 0 1 1 0 3 1 1 0 1 0 4 0 1 1 0 1 5 0 0 0 1 0

Observaţii:

1. Pentru n ţări, matricea este pătratică, are n linii şi n coloane

2. Pe diagonala principală elementele sunt nule, A[i, i] = 0 * ţara ti nu se învecinează cu ea însăşi

3. Matricea este simetrică, adică A[i,j] = A[j, i] * dacă ţara ti se invecinează cu ţara tj atunci şi tj se

învecinează cu ti.

Teorema colorării hărţilor: Orice hartă plană poate colorată folosind cel mult 4 culori

Reprezentarea soluţiei: - soluţia are n componente, unde n este numărul de ţări

-fiecare componentă xk are valori în mulţimea {A, B, C, D}

Condiţia de validare: - soluţia nu are continuare dacă două ţări vecine sunt colorate la fel

Prima soluţie: A, B, C, A, B

Vecinii sunt: ţara 1: 2, 3 ţara 2: 1, 3, 4 ţara 3: 1,2,4 ţara 4: 2, 3, 5 ţara 5: 4

Varianta recursivă

1. #include<iostream> 2. #include<fstream> 3. using namespace std; 4. int A[21][21]; 5. char x[21]; 6. int n,nr; 7. ifstream fin("harta.in"); 8. 9. void citire() 10. { 11. int i,j; 12. fin>>n; 13. for(i=1;i<=n;i++) 14. for(j=1;j<=n;j++) 15. fin>>A[i][j]; 16. } 17. 18. void tipar() 19. { 20. int i; 21. nr++; 22. for(i=1;i<=n;i++) 23. cout<<x[i]; 24. cout<<'\n'; 25. } 26. 27. int valid(int k) 28. { 29. int i; 30. for(i=1;i<k;i++) 31. if((A[i][k]==1)&&(x[i]==x[k])) 32. return 0; 33. return 1; 34. } 35. 36. void back(int k) 37. { 38. char c; 39. if(k==n+1) tipar(); 40. else 41. for(c='A';c<='D';c++) 42. { 43. x[k]=c; 44. if(valid(k)) back(k+1); 45. } 46. } 47. 48. int main() 49. { 50. citire(); 51. back(1); 52. cout<<nr<<" solutii"; 53. fin.close(); 54. return 0; 55. }