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

Narysuj ślad

iOryginalna treść zadania jest dostępna tutaj

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

Rozwiązanie

W celu uzyskania listy instrukcji potrzebujemy funkcję, która po otrzymaniu ciągu znaków rozdzieli nam go na kolejne elementy listy. W tym celu funkcja split (ang. rodziel) wykorzysta klasę stringstream i vector. Pierwsze zostanie użyte do rozdzielenia elementów, a drugi pozwoli nam przechowywać zebrane dane.

  1. vector<string> &split(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. }
  9. vector<string> split(const string &s, char d) {
  10.   vector<string> l;
  11.   split(s, d, l);
  12.   return l;
  13. }

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 toInt(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 expand(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 main()

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ęść wywołuje funkcję split, aby pobrany ciąg znaków zamienić w listę instrukcji, które zostaną pobrane w części trzeciej.

  1.   cout << "Podaj dane: ";
  2.   getline( cin, wyraz );
  3.   vector<string> lista = split(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ę expand, aby uniknąć problemów z wyjściem poza zakres tablicy.

  1.   for(int i = 0; i < lista.size(); i++){
  2.     f = lista[i][0];
  3.     r = toInt(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.       expand(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.

  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.

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