Potwory Znakolandii

Treść

Oryginalna treść zadania

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

• typ „0” (tzw. cyfrojad) – ich głównym przysmakiem są cyfry, inne znaki pomijają, bo ich nie trawią, nie potrafią przestać jeść giną jeśli zjedzą naraz więcej niż 5 cyfr,
• typ „a” (tzw. literojad) – to stworzenia, które uwielbiają wszystkie litery, niestety wielkie litery szkodzą im jeśli zjedzą ich więcej niż 5 podczas jednego posiłku to giną,
• typ „*” (tzw. znakojad) – to najbardziej przerażające istoty, które potrafią zjeść dosłownie każdy znak, jednak łączenie wszystkich posiłków im szkodzi: jeśli zjedzą naraz co najmniej 5 cyfr więcej niż znaków różnych od cyfr to giną,

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

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

• Kod źródłowy Rozwiązanie