fork download 
  1. #include <cstdio>
  2. #include <string>
  3. #include <vector>
  4. #include <ctime>
  5. #include <cmath>
  6. using namespace std;
  7.  
  8. int read() { int n; scanf("%d", &n); return n; }
  9.  
  10. /*
  11.  *  Polom diagramu przypisujemy identyfikatory (id) od 0 do 18.
  12.  *  To będzie kolejność, w której będziemy wypełniać pola.
  13.  *
  14.  *    18   7   8
  15.  *  17   2   4   9
  16.  *16   1   0   5  10
  17.  *  15   3   6  11
  18.  *    14  13  12
  19.  *
  20.  */
  21.  
  22. const int n = 19;
  23. const int roznica = 5; // to minimalna różnica wartości w sąsiednich polach
  24. int diagram[n]; // tu będziemy wpisywać wartości umieszczane w poszczególnych polach
  25.  
  26. // tutaj dla każdego pola umieszczamy listę pól-sąsiadów o mniejszych id
  27. // każda lista zakończona jest wartością ujemną (-1)
  28. int s0[] = {-1};
  29. int s1[] = {0, -1};
  30. int s2[] = {0, 1, -1};
  31. int s3[] = {0, 1, -1};
  32. int s4[] = {0, 2, -1};
  33. int s5[] = {0, 4, -1};
  34. int s6[] = {0, 3, 5, -1};
  35. int s7[] = {2, 4, -1};
  36. int s8[] = {4, 7, -1};
  37. int s9[] = {4, 5, 8, -1};
  38. int s10[] = {5, 9, -1};
  39. int s11[] = {5, 6, 10, -1};
  40. int s12[] = {6, 11, -1};
  41. int s13[] = {3, 6, 12, -1};
  42. int s14[] = {3, 13, -1};
  43. int s15[] = {1, 3, 14, -1};
  44. int s16[] = {1, 15, -1};
  45. int s17[] = {1, 2, 16, -1};
  46. int s18[] = {2, 7, 17, -1};
  47.  
  48. // tu definiujemy tablice tablica sąsiadów (powyższych list)
  49. int *sasiad[] = { s0, s1, s2, s3, s4, s5, s6, s7, s8, s9, s10, s11, s12, s13, s14, s15, s16, s17, s18};
  50.  
  51. // tu tablica, w której oznaczamy, czy dana wartość została już wpisana do diagramu (0 - nie wpisana, 1 - wpisana)
  52. int wpisana[n+1];
  53.  
  54. // te zmienne zliczają liczbę rozwiązań oraz liczbę wywołań funkcji rekurencyjnej
  55. int liczbaRozwiazan;
  56. int liczbaWywolanRekurencyjnych;
  57.  
  58. // przełącznik, do utożsamiania rozwiązań identycznych z punku widzenia symetrii i obrotów
  59. const bool utozsamRozwiazania = false;
  60. //const bool utozsamRozwiazania = true;
  61.  
  62. // tu funkcja, która próbuje wypełnić pole o danym id kolejnymi wartościami od 1 do 19
  63. // jeśli jakaś wartość nie pasuje, to jest pomijana
  64. // jeśli wartość pasuje, to jest wpisywana i funkcja wywołuje się rekurencyjnie dla kolejnego id
  65. // po sprawdzeniu wszystkich wartości funkcja kończy się, wtedy sterowanie wraca do funkcji o id mniejszym o jeden i tam jest próbowana kolejna wartość
  66. // koniec wywałań rekurencyjnych następuje, gdy funkcja dostanie id = 19 - to oznacza, że diagram został poprawnie wypełniony
  67.  
  68. void wypelnij(int id)
  69. {
  70.     liczbaWywolanRekurencyjnych++;
  71.  
  72.     if (id == n) { // mamy rozwiązanie
  73.         liczbaRozwiazan++;
  74.         // tu można jeszcze np. wypisać sobie rozwiązanie
  75.         return;
  76.     }
  77.  
  78.     for (int x=1; x<=n; ++x) {
  79.  
  80.         if (wpisana[x] == 1) continue; // liczba x jest juz wpisana w inne pole diagramu, idziemy do następnego x
  81.  
  82.         bool error = false;
  83.         for (int j=0; sasiad[id][j] >= 0; ++j) {
  84.             if (std::abs(x - diagram[sasiad[id][j]]) < roznica) { // std::abs zwraca wartość bezwzględną liczby
  85.                 error = true;
  86.                 break;
  87.             }
  88.         }
  89.         if (error) continue; // liczba x nie moze byc wpisana w pole id, bo jeden z sąsiadów ma już wpisaną wartość zbyt bliską wartości x, idziemy do następnego x
  90.  
  91.         if (utozsamRozwiazania) {
  92.             // ten warunek utożsamia obroty jako jedno rozwiązanie - tzn. zakładamy, że spośród sasiadów pola id=0 największą wartość ma pole id=1
  93.             if (2 <= id && id <= 6) if (x > diagram[1]) continue;
  94.             // a ten warunek utożsamia odbicia symetryczne - tzn. zakładamy, że pole id=2 ma większą wartość niż pole id=3
  95.             if (id == 3) if (x > diagram[2]) continue;
  96.         }
  97.  
  98.         // wartość x możemy wpisać w pole id
  99.         diagram[id] = x; // wpisujemy liczbę x do diagramu
  100.         wpisana[x] = 1; // oznaczamy wartość x jako wykorzystaną
  101.         wypelnij(id + 1); // przechodzimy rekurencyjnie do wypełniania kolejnego pola
  102.         wpisana[x] = 0; // wymazujemy x z diagramu
  103.         // ... i sprawdzamy kolejną wartość x (w następnej iteracji pętli)
  104.     }
  105. }
  106.  
  107. int main()
  108. {
  109.     time_t startTime = time(NULL);
  110.  
  111.     liczbaRozwiazan = 0;
  112.     liczbaWywolanRekurencyjnych = 0;
  113.     for (int x=1; x<=n; ++x) wpisana[x] = 0;
  114.  
  115.     wypelnij(0);
  116.  
  117.     time_t endTime = time(NULL);
  118.  
  119.     printf("Liczba rozwiazan: %d\n", liczbaRozwiazan);
  120.     printf("Liczba wywolan rekurencyjnych: %d\n", liczbaWywolanRekurencyjnych);
  121.     printf("Czas dzialania programu (z dokladnoscia do 1 sekundy): %d sekund\n", endTime - startTime);
  122.  
  123.     return 0;
  124. }
  125.  
  126.  
  127.  
Success #stdin #stdout 7.78s 3460KB
comments ()
stdin 
Standard input is empty
stdout 
Liczba rozwiazan: 36780
Liczba wywolan rekurencyjnych: 43258222
Czas dzialania programu (z dokladnoscia do 1 sekundy): 8 sekund
https://ideone.com/BDTFdc
language:
C++ (gcc 8.3)
created:
8 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!