fork download
  1. #include <iostream>
  2. #define SIZE 100
  3.  
  4. using namespace std;
  5.  
  6. int stack[SIZE];
  7. int A[SIZE][SIZE];
  8. int level, n, k; // n = număr de țări, k = număr de culori
  9.  
  10. int sol() {
  11. return level == n;
  12. }
  13.  
  14. void init() {
  15. stack[level] = 0;
  16. }
  17.  
  18. int succ() {
  19. if (stack[level] < k) {
  20. stack[level]++;
  21. return 1;
  22. }
  23. return 0;
  24. }
  25.  
  26. int valid() {
  27. for (int i = 1; i <= level - 1; ++i) {
  28. if (stack[i] == stack[level] && A[i][level] == 1)
  29. return 0;
  30. }
  31. return 1;
  32. }
  33.  
  34. void display_solution() {
  35. cout << "Solutie gasita:\n";
  36. for (int i = 1; i <= n; ++i) {
  37. cout << "Tara " << i << " are culoarea: " << stack[i] << endl;
  38. }
  39. cout << endl;
  40. }
  41.  
  42. void backtracking() {
  43. int s, v;
  44. level = 1;
  45.  
  46. while (level > 0) {
  47. s = 1;
  48. v = 0;
  49.  
  50. while (s && !v) {
  51. s = succ();
  52. if (s)
  53. v = valid();
  54. }
  55.  
  56. if (s) {
  57. if (sol()) {
  58. display_solution();
  59. } else {
  60. level++;
  61. init();
  62. }
  63. } else {
  64. level--;
  65. }
  66. }
  67. }
  68.  
  69. int main() {
  70. cout << "Numar de tari: ";
  71. cin >> n;
  72.  
  73. cout << "Numar de culori: ";
  74. cin >> k;
  75.  
  76. // Initializare matrice cu 0
  77. for (int i = 1; i <= n; ++i)
  78. for (int j = 1; j <= n; ++j)
  79. A[i][j] = 0;
  80.  
  81. // Citire matrice de adiacenta (doar sub diagonala)
  82. for (int i = 1; i <= n; ++i) {
  83. for (int j = 1; j < i; ++j) {
  84. cout << "Exista granita intre tara " << i << " si tara " << j << "? (1/0): ";
  85. cin >> A[i][j];
  86. A[j][i] = A[i][j]; // simetric
  87. }
  88. }
  89.  
  90. // Inițializare primă poziție
  91. init();
  92.  
  93. // Pornim backtracking
  94. backtracking();
  95.  
  96. return 0;
  97. }
  98.  
  99. /*
  100. Numar de tari: 4
  101. Numar de culori: 3
  102. Exista granita intre tara 2 si tara 1? (1/0): 1
  103. Exista granita intre tara 3 si tara 1? (1/0): 1
  104. Exista granita intre tara 3 si tara 2? (1/0): 0
  105. Exista granita intre tara 4 si tara 1? (1/0): 1
  106. Exista granita intre tara 4 si tara 2? (1/0): 1
  107. Exista granita intre tara 4 si tara 3? (1/0): 1
  108.  
  109. */
Success #stdin #stdout 0s 5316KB
stdin
4
3
1
1
0
1
1
stdout
Numar de tari: Numar de culori: Exista granita intre tara 2 si tara 1? (1/0): Exista granita intre tara 3 si tara 1? (1/0): Exista granita intre tara 3 si tara 2? (1/0): Exista granita intre tara 4 si tara 1? (1/0): Exista granita intre tara 4 si tara 2? (1/0): Exista granita intre tara 4 si tara 3? (1/0): Solutie gasita:
Tara 1 are culoarea: 1
Tara 2 are culoarea: 2
Tara 3 are culoarea: 2
Tara 4 are culoarea: 3

Solutie gasita:
Tara 1 are culoarea: 1
Tara 2 are culoarea: 2
Tara 3 are culoarea: 3
Tara 4 are culoarea: 3

Solutie gasita:
Tara 1 are culoarea: 1
Tara 2 are culoarea: 3
Tara 3 are culoarea: 2
Tara 4 are culoarea: 2

Solutie gasita:
Tara 1 are culoarea: 1
Tara 2 are culoarea: 3
Tara 3 are culoarea: 3
Tara 4 are culoarea: 2

Solutie gasita:
Tara 1 are culoarea: 2
Tara 2 are culoarea: 1
Tara 3 are culoarea: 1
Tara 4 are culoarea: 3

Solutie gasita:
Tara 1 are culoarea: 2
Tara 2 are culoarea: 1
Tara 3 are culoarea: 3
Tara 4 are culoarea: 3

Solutie gasita:
Tara 1 are culoarea: 2
Tara 2 are culoarea: 3
Tara 3 are culoarea: 1
Tara 4 are culoarea: 1

Solutie gasita:
Tara 1 are culoarea: 2
Tara 2 are culoarea: 3
Tara 3 are culoarea: 3
Tara 4 are culoarea: 1

Solutie gasita:
Tara 1 are culoarea: 3
Tara 2 are culoarea: 1
Tara 3 are culoarea: 1
Tara 4 are culoarea: 2

Solutie gasita:
Tara 1 are culoarea: 3
Tara 2 are culoarea: 1
Tara 3 are culoarea: 2
Tara 4 are culoarea: 2

Solutie gasita:
Tara 1 are culoarea: 3
Tara 2 are culoarea: 2
Tara 3 are culoarea: 1
Tara 4 are culoarea: 1

Solutie gasita:
Tara 1 are culoarea: 3
Tara 2 are culoarea: 2
Tara 3 are culoarea: 2
Tara 4 are culoarea: 1