Narysuj Ślad

Oryginalna 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:

R9 D6 L9 U4 R7 D2 L5

wynikiem powinno być:

0000000000
_________0
00000000_0
0______0_0
0_000000_0
0________0
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.

vector<string>& podziel(const string &s, char d, vector<string> &elems) {
    stringstream ss(s);
    string i;
    while (getline(ss, i, d)) {
        elems.push_back(i);
    }
    return elems;
}

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

vector<string> podziel(const string &s, char d) {
    vector<string> l;
    podziel(s, d, l);
    return l;
}

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:

int naInt(string str) {
    int i;
    istringstream iss(str);
    iss >> i;
    return i;
}

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ą:

void rozszerz(vector< vector< char > > &tab, int ax, int ay) {
    if (tab[0].size() <= ax)
        for (int i = 0; i < tab.size(); i++)
            for (int j = tab[i].size(); j <= ax; j++)
                tab[i].push_back(-1);
    if (tab.size() <= ay)
        for (int i = tab.size(); i <= ay; i++) {
            tab.push_back(vector< char >(0));
            for (int j = 0; j < tab[0].size(); j++)
                tab[i].push_back(-1);
        }
}

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.

W celu optymalizacji wykorzystania pamięci program będzie automatycznie poszerzał tablicę jeśli zaistnieje taka potrzeba. Do tego będzie służyć funkcja poszerz(), która podaną tablicę tab i pozycji (ax,ay) upewni się, że tablica nie jest za mała.

        static void poszerz(ref List<List<char>> tab, int ax, int ay) {
            if (tab.Count <= ay)
                for (int i = tab.Count; i <= ay; i++) {
                    tab.Add(new List<char>(0));
                    for (int j = 0; j < tab[0].Count; j++)
                        tab[i].Add('\0');
                }
            if (tab[0].Count <= ax)
                for (int i = 0; i < tab.Count; i++)
                    for (int j = tab[i].Count; j <= ax; j++)
                        tab[i].Add('\0');
        }

Funkcja pomocnicza porownaj() będzie porównywać dwa znaki i zwracać 1 jeśli są identyczne i 0 jeśli nie. Będzie ona wykorzystywana do określania przesunięcia śladu.

        static int porownaj(char a, char b) {
            return (a == b) ? 1 : 0;
        }

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.

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

        static void Main(string[] args) {
            List<List<char>> tab = new List<List<char>>();
            int ax = 0, ay = 0, r;
            char f;
            string wyraz;

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

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

            Console.WriteLine("Podaj dane:");
            wyraz = Console.ReadLine();
            string[] lista = wyraz.Split(' ');

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.

    for (int i = 0; i < lista.size(); i++) {
        f = lista[i][0];
        r = naInt(lista[i].substr(1, lista[i].length() - 1));
        while (r-- > 0) {
            ax += (f == 'U') * -1 + (f == 'D');
            ay += (f == 'L') * -1 + (f == 'R');
            rozszerz(tab, ay, ax);
            tab[ax][ay] = 0;
        }
    }

            for (int i = 0; i < lista.Length; i++) {
                f = lista[i][0];
                r = Convert.ToInt32(lista[i].Substring(1, lista[i].Length - 1));
                while (r-- > 0) {
                    ax += porownaj(f, 'U') * -1 + porownaj(f, 'D');
                    ay += porownaj(f, 'L') * -1 + porownaj(f, 'R');
                    poszerz(ref tab, ay, ax);
                    tab[ax][ay] = '0';
                }
            }

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

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

            for (int y = 0; y < tab.Count; y++) {
                for (int x = 0; x < tab[y].Count; x++)
                    Console.Write(((tab[y][x] == '\0') ? '_' : '0'));
                Console.WriteLine();
            }

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.

    system("PAUSE");
    return 0;
}

            Console.ReadKey();
        }