Strona główna » Algorytmy » Artykuły » Narysuj Ślad
 

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.

C++
C#
  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.

C++
C#
  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:

C++
C#
  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ą:

C++
C#
  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.

C++
C#
  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.

C++
C#
  1.   cout << "Podaj dane: ";
  2.   getline(cin, wyraz);
  3.   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.

C++
C#
  1.   for (int i = 0; i < lista.size(); i++) {
  2.     f = lista[i][0];
  3.     r = naInt(lista[i].substr(1, lista[i].length() - 1));
  4.     while (r-- > 0) {
  5.       ax += (f == 'U') * -1 + (f == 'D');
  6.       ay += (f == 'L') * -1 + (f == 'R');
  7.       rozszerz(tab, ay, ax);
  8.       tab[ax][ay] = 0;
  9.     }
  10.   }

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

C++
C#
  1.   for (int y = 0; y < tab.size(); y++) {
  2.     for (int x = 0; x < tab[y].size(); x++)
  3.       cout << ((tab[y][x] == -1) ? '_' : '0');
  4.     cout << endl;
  5.   }

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.

C++
C#
  1.   system("PAUSE");
  2.   return 0;
  3. }