Narysuj Ślad

Treść

Narysuj linie podążając za prostymi wskazówkami. Na wejściu otrzymujemy instrukcje rozdzielone znakiem spacji. Każda instrukcja składa się z litery (U, D, L lub R co oznacza kolejno w górę, w dół, w lewo, w prawo) oraz liczby.

Zadanie polega na narysowaniu linii podążając za wskazówkami. Rysowanie zaczyna się od lewego-górnego rogu. Nieodwiedzone pola należy przedstawić podkreślnikiem \'_\', a odwiedzone \'0\'. Pola mogą być odwiedzona dwukrotnie. Przykładowo dla:

1. R9 D6 L9 U4 R7 D2 L5

wynikiem powinno być:

1. 0000000000
2. _________0
3. 00000000_0
4. 0______0_0
5. 0_000000_0
6. 0________0
7. 0000000000

Implementacja

Spostrzeżenia

Tablica powinna być dynamiczna, aby uniknąć podwójnego przeglądania ciągu instrukcji. Potrzebujemy wyodrębnić instrukcje z pobranej wejściowej linijki tekstu, ponieważ nie mamy podane ile instrukcji łącznie będzie.

Rozwiązanie

W celu uzyskania listy instrukcji potrzebujemy funkcję, która po otrzymaniu ciągu znaków rozdzieli nam go na kolejne elementy listy. Funkcja podziel() rozdziela elementy wczytane z konsoli.

1. vector<string>& podziel(const string &s, char d, vector<string> &elems) {
2.   stringstream ss(s);
3.   string i;
4.   while (getline(ss, i, d)) {
5.     elems.push_back(i);
6.   }
7.   return elems;
8. }

Funkcja nadrzędna przyjmuje jeden argument mniej i odpowiada za przygotowanie wektora do konwersji danych.

1. vector<string> podziel(const string &s, char d) {
2.   vector<string> l;
3.   podziel(s, d, l);
4.   return l;
5. }

Potrzebujemy również funkcji, która pozwoli nam skonwertować ciąg znaków string na zmienną int. W tym celu również posłużymy się zmienną stringstream:

1. int naInt(string str) {
2.   int i;
3.   istringstream iss(str);
4.   iss >> i;
5.   return i;
6. }

Ostatnia funkcja pomocnicza będzie dotyczyć bezpośrednio tablicy w której będziemy zapisywać dane. W C++ wyjście poza granice wyznaczone przez funkcję wywoła błąd, który przerwie działanie programu, dlatego potrzebujemy funkcji, która pozwoli nam dynamicznie rozszerzać ją:

1. void rozszerz(vector< vector< char > > &tab, int ax, int ay) {
2.   if (tab[0].size() <= ax)
3.     for (int i = 0; i < tab.size(); i++)
4.       for (int j = tab[i].size(); j <= ax; j++)
5.         tab[i].push_back(-1);
6.   if (tab.size() <= ay)
7.     for (int i = tab.size(); i <= ay; i++) {
8.       tab.push_back(vector< char >(0));
9.       for (int j = 0; j < tab[0].size(); j++)
10.         tab[i].push_back(-1);
11.     }
12. }

Jej działanie sprowadza się przede wszystkie do porównania obecnej wielkości tablicy z podanymi dodatkowo parametrami. Jeśli tablica jest za mała to nastąpi jej rozszerzenie. W przypadku, gdy jest za mało kolumn to do każdego elementu listy dodanie nowej z wartością pola nieodwiedzonego. W przypadku, gdy jest za mało wierszy to zostanie dodany nowy o takiej samej ilości kolumn co wszystkie pozostałe.

Funkcja Główna

W głównej funkcji następuje deklaracja zmiennych, których będziemy uzywać: tab - będzie przechowywać tablicę pól, które zostały (nie)odwiedzone, ax i ay - współrzędne aktualnego położenia rysowania, r - zmienna pomocnicza mówiąca ile pól należy przesunąć w daną stronę, f - zmienna przechowująca kierunek określony w instrukcji oraz lista, która przechowuje instrukcje zawarte w wprowadzonej linijce tekstu.

1. int main() {
2.   vector< vector< char > > tab(1, vector<char>(1, false));
3.   int ax = 0, ay = 0, r;
4.   char f;
5.   string wyraz;

Druga część wczytuje dane i rozdziela tak, aby każda komenda była dostępna na liście jako oddzielny element.

6.   cout << "Podaj dane: ";
7.   getline(cin, wyraz);
8.   vector<string> lista = podziel(wyraz, ' ');

Część trzecia to pętla wywoływana dla każdego elementu z listy. Najpierw rozbija instrukcje na zmienne i zapisuje do f określony kierunek i do r ilość kroków. Następnie póki kroki się nie skończą zmieniane są wartości współrzędnych ax i ay. Przed przypisywaniem w danym polu wartości odwiedzenia wywołujemy funkcję rozszerz(), aby uniknąć problemów z wyjściem poza zakres tablicy.

9.   for (int i = 0; i < lista.size(); i++) {
10.     f = lista[i][0];
11.     r = naInt(lista[i].substr(1, lista[i].length() - 1));
12.     while (r-- > 0) {
13.       ax += (f == 'U') * -1 + (f == 'D');
14.       ay += (f == 'L') * -1 + (f == 'R');
15.       rozszerz(tab, ay, ax);
16.       tab[ax][ay] = 0;
17.     }
18.   }

Czwarta część jest to wypisywanie wyniku. To właśnie tu określamy jak dana wartość pola ma być interpretowana.

19.   for (int y = 0; y < tab.size(); y++) {
20.     for (int x = 0; x < tab[y].size(); x++)
21.       cout << ((tab[y][x] == -1) ? '_' : '0');
22.     cout << endl;
23.   }

Kończymy pracę programu wpierw zatrzymując wykonywanie programu, aby użytkownik mógł przeczytać wyjście, a po naciśnięciu dowolnego przycisku program jest zamykany.

24.   system("PAUSE");
25.   return 0;
26. }

• Kod źródłowy Implementacja