Strona główna » C++ » Zadania » Potwory Znakolandii
 

Potwory Znakolandii

Treść

Oryginalna treść zadania

W Znakolandii, planetę AUI#678 zamieszkują potwory. Wśród znakojadów wyróżniono kilka gatunków:

Potwory są wieczne głodne, dlatego jeśli odkryją nowe wolne miejsce przeprowadzą się do niego, a następnego dnia zjedzą cały dostępny posiłek. Jeśli podczas niego zginą to zostają w danym miejscu na zawsze. Po spustoszeniu regionu i w przypadku braku wolnego niepustego miejsca potwory opuszczają nie zamieszkują żadnego miejsca.

Region to zbiór miejsc, który zawiera miejsca, które mają ciąg znaków, który określa rodzaj posiłku tam się znajdującego. Drugiego dnia potwór pustoszy miejsce z całego posiłku, więc z ciągu znaków zostaje tylko ‘\0’ i od razu szuka kolejnego miejsca z posiłkiem bez żadnego potwora (żywego czy martwego).

Zadania do wykonania

  1. Stwórz strukturę miejsce, która będzie przechowywać rodzaj posiłku znajdującego się w nim, unikalny numer oraz to czy znajduje się tam jakiś potwór (żywy lub martwy).
  2. Napisz funkcję sprawdzMiejsce(), która jako argument przyjmie miejsce i sprawdzi czy nie mieszka potwór oraz czy jest tam dostępne pożywienie.
  3. Stwórz strukturę potwór, która będzie przechowywać imię potwora, wskaźnik do miejsca gdzie się znajduje, ile zjadł znaków do tej pory, jego gatunek oraz czy żyje.
  4. Napisz funkcję nakarm(), która będzie przyjmowała napis oraz potwora, która biorąc pod uwagę sposób odżywiania się gatunku doda ile znaków zjadł stwór lub go uśmierci.
  5. Napisz funkcję przeprowadzPotwora(), która przeniesie potwora do następnego dostępnego miejsca w regionie. Jeśli takie nie istnieje potwór nie powinien mieć przypisanego miejsca.
  6. Napisz funkcję wypisz potwora(), która poda w jednej linii jego imię, gatunek, ile zjadł znaków oraz czy żyje.
  7. Napisz funkcję main(), która:
    1. Wczyta liczbę n i m, n określi ile istnieje miejsc na planecie, a m określi ile istniej potworów na planecie
    2. Wczyta n ciągów znaków długości nie przekraczającej 40 znaków, które będą oznaczały jaki posiłek tam się znajduje
    3. Wczyta m potwór, gdzie jeden potwór to jedna linia tekstu o maksymalnej długości 15, gdzie ostatni znak określa gatunek potwora, ale nie należy do imienia, m-ty potwór zostać przypisany do m-tego miejsca. Zakładamy, że potwory wchodzą z pustym żołądkiem i żyje.
    4. Uruchom pętle, której każda iteracja będzie oznaczała jeden dzień i jeśli potwór znajduje się w niespustoszonym miejscu to go nakarmi, a jeśli w pustoszonym to go przeprowadzi do następnego wolnego miejsca. Program się kończy, gdy ostatnie miejsce zostanie spustoszone. Można założyć, że dane są poprawne i do takiego zdarzenia dojdzie.
    5. Na koniec program powinien wypisać stan każdego potwora.

Przykłady

Przykład 1

Dla danych:

  1. 2 1
  2. UIOFSR34HJK3
  3. HJBN78945%KL
  4. ZNAKOJAD*

otrzymamy:

  1. ZNAKOJAD*24ZYJE

Przykład 2

Dla danych:

  1. 3 2
  2. 74309436WerO
  3. UI%%R3dherf3
  4. HJsd78945%KL
  5. CYFROJAD0
  6. LITEROJADa
Otrzymamy:
  1. CYFROJAD08NIE ZYJE
  2. LITEROJADa14ZYJE

Dodatkowe uwagi

Program powinien prawidłowo zwalniać dynamicznie zaalokowaną pamięć.

Rozwiązanie

Poniżej znajduje się pełne rozwiązanie zadania razem z komentarzem:

  1. #include <iostream>
  2. using namespace std;
  3. struct miejsce{
  4.   char* posilek;  // Jaki posiłek się znajduje na miejscu
  5.   int index;    // Unikalny indeks miejsca
  6.   bool potwor;  // Czy mieszka tam potwór
  7. };
  8. struct potwor{
  9.   char* imie;  // Imię potwora
  10.   miejsce* lokalizacja;  // Wskaźnik na lokalizacje z regionu
  11.   int znakow_zjedzonych;  // Ile zostało zjedzonych znaków przez potwora
  12.   char gatunek;  // Gatunek potwowa
  13.   bool zyje;  // Czy potwór żyje
  14. };
  15. bool sprawdzMiejsce(miejsce* m);
  16. void nakarm(potwor* p);
  17. void przeprowadzPotwora(miejsce** miejsca, int n, potwor* p);
  18. int main () {
  19.   // Wczytujemy miejsca w regionie
  20.   int n, m;
  21.   cin >> n >> m;
  22.   cin.ignore();
  23.   miejsce** miejsca = new miejsce*[n];
  24.   for(int i = 0; i < n; i++){
  25.     miejsce* m = new miejsce;
  26.     char* data = new char[41];
  27.     cin.getline(data, 41);
  28.     m->index = i;
  29.     m->potwor = false;
  30.     m->posilek = data;
  31.     miejsca[i] = m;
  32.   }
  33.   // Wczytujemy wszystkie potwory
  34.   potwor** potwory = new potwor*[n];
  35.   for(int i = 0; i < m; i++){
  36.     potwor* p = new potwor;
  37.     char* data = new char[16];
  38.     cin.getline(data, 16);
  39.     int dlugosc = strlen(data);
  40.     p->gatunek = data[dlugosc-1];
  41.     data[dlugosc-1]='\0';
  42.     p->imie = data;
  43.     p->lokalizacja = miejsca[i];
  44.     p->znakow_zjedzonych = 0;
  45.     p->zyje = true;
  46.     potwory[i] = p;
  47.   }
  48.   // Wykonujemy kolejne dni iteracji
  49.   while(miejsca[n-1]->posilek[0] != '\0'){
  50.     for(int i = 0; i < m; i++){
  51.       if(potwory[i]->zyje){
  52.         nakarm(potwory[i]);
  53.         przeprowadzPotwora(miejsca, n, potwory[i]);
  54.       }
  55.     }
  56.   }
  57.   // Wypisujemy wszystkie potwory
  58.   for(int i = 0; i < m; i++){
  59.     cout << potwory[i]->imie << "\t" << potwory[i]->gatunek << "\t" << potwory[i]->znakow_zjedzonych << "\t" << (potwory[i]->zyje ? "ZYJE" : "NIE ZYJE") << endl;
  60.   }
  61.   // Zwalniamy pamięć
  62.   for(int i = 0; i < n; i++){
  63.     delete[] miejsca[i]->posilek;
  64.   }
  65.   delete[] miejsca;
  66.   for(int i = 0; i < m; i++){
  67.     delete[] potwory[i]->imie;
  68.   }
  69.   delete[] potwory;
  70.   system ("pause");
  71.   return 0;
  72. }
  73. // Prawda jeśli nie mieszka żaden potwór i znajduje się tam posiłek.
  74. bool sprawdzMiejsce(miejsce* m){
  75.   return (!m->potwor || m->posilek[0] != '\0');
  76. }
  77. // Karmi potwora na podstawie jego lokalizacji
  78. void nakarm(potwor* p){
  79.   // W celu uproszczenia zapisu zdobywamy wksaźnik na lokalizacje
  80.   char* napis = p->lokalizacja->posilek;
  81.   if(p->gatunek == '0'){
  82.       // Zliczamy ile zje cyfrojad cyfr
  83.       int licznik = 0, i = 0;
  84.       while(napis[i]){
  85.         if(napis[i]>='0' && napis[i]<='9')
  86.           licznik++;
  87.         i++;
  88.       }
  89.       p->znakow_zjedzonych += licznik;
  90.       // Jeśli zjadł więcej niż 5 cyfr to uśmierć
  91.       if(licznik > 5){
  92.         p->zyje=false;
  93.       }
  94.   } else if (p->gatunek == 'a') {
  95.       // Zliczamy ile zje literojad mały i wielkich liter
  96.       int licznik_a = 0, licznik_A = 0, i = 0;
  97.       while(napis[i]){
  98.         if(napis[i]>='a' && napis[i]<='z')
  99.           licznik_a++;
  100.         if(napis[i]>='A' && napis[i]<='Z')
  101.           licznik_A++;
  102.         i++;
  103.       }
  104.       p->znakow_zjedzonych += licznik_a + licznik_A;
  105.       // Jeśli zjadł więcej niż 5 wielkich liter to uśmierć
  106.       if(licznik_A > 5){
  107.         p->zyje=false;
  108.       }
  109.   } else {
  110.       // Zliczamy ile zje cyfr i innych znaków
  111.       int licznik_0 = 0, licznik_ = 0, i = 0;
  112.       while(napis[i]){
  113.         if(napis[i]>='0' && napis[i]<='9')
  114.           licznik_0++;
  115.         else
  116.           licznik_++;
  117.         i++;
  118.       }
  119.       p->znakow_zjedzonych += licznik_0 + licznik_;
  120.       // Jeśli zjadł więcej o 5 cyfr niż znaków to uśmierć
  121.       if(licznik_0 > licznik_ + 5){
  122.         p->zyje=false;
  123.       }
  124.   }
  125.   // Zamień pierwszy znak, aby zaznaczyć, że posiłek jest pusty
  126.   p->lokalizacja->posilek[0]='\0';
  127. }
  128. // Przeprowadza potwora do nowej wolnej lokalizacji
  129. void przeprowadzPotwora(miejsce** miejsca, int n, potwor* p){
  130.   // Pobierz starą lokalizację i przywróć domyślne ustawienia zmiennych
  131.   int indeks = p->lokalizacja->index;
  132.   p->lokalizacja = NULL;
  133.   miejsca[indeks]->potwor = false;
  134.   indeks++;
  135.   // Szukaj nowej wolnej lokalizacji
  136.   while(!sprawdzMiejsce(miejsca[indeks]) && indeks < n){
  137.     indeks++;
  138.   }
  139.   // Jeśli indeks != n to znaczy, że istnieje nowa wolna lokzalizacja w regionie
  140.   if(indeks != n){
  141.     p->lokalizacja = miejsca[indeks];
  142.     miejsca[indeks]->index = true;
  143.   }
  144. }