5. Poriadna výzva vzorové riešenie

9 9 15
zapamkacg
kkjadrorn
ioyrylati
askznmaes
stssaiyhu
erttmjpsl
railistrk
dkonkalvy
aaskatsec
adresa
cesta
cyklus
dynamika
gramatika
halda
jadro
jazyk
kostra
list
mapa
mys
skok
tok
vlakno

zacniriesitprask

5 4 3
ccxb
xabf
xaxf
xaxf
xaxf
abb
aaaa
cc

xxfxxfxxfxxf

Vzorové riešenie tohto príkladu je písané spôsobom, ktorý ho umožňuje čítať postupne, po sadách. Ak vás teda úloha bavila a stále by ste ju chceli vyriešiť, ale neviete si s ňou dať rady, odporúčame prečítať vzorové riešenie iba po sadu, na ktorej ste sa zasekli. Odtiaľ potom zapojiť mozgové závity a skúsiť úlohu doriešiť bez ďaľšej pomoci. Ak už chcete mať tento príklad za sebou alebo sa tešíte na úplny vzorák, môžete ho samozrejme prečítať celý na jeden raz.

A teraz sa už pozrime na myšlienku riešenia. Riešenie je vcelku priamočiare, vyhľadaniu slov v osemsmerovke sa nemáme ako vyhnúť. Neostáva nám preto nič iné ako zvoliť vhodnú implementáciu. Samozrejme, zložitosť vyhľádavania, ktorú bude riešenie vyžadovať sa bude v jednotlivých sadách líšiť.

Predtým, než skočíme na samotné riešenie súťažnej úlohy a implementáciu, bolo by vhodné si ukázať ako v tejto úlohe (a v typovo podobných), šikovne a jednoducho načítať a uložiť dáta zo vstupu.

string

V C++ existuje na uloženie reťazca znakov dátova štruktúra s názvom string. Na string sa v skutočnosti môžeme pozrieť iba ako na pole charov. Vieme sa v ňom, rovnako ako v poli, pozrieť na jednotlivé indexy a zistiť, aký znak sa na nich nachádza.

Samozrejme, ak by bol string iba pole charov (char[]), nebol by ničím zaujímavý. Prináša nám teda isté výhody. Do premennej tohto typu môžeme načítavať rovnako ľahko ako do premennej typu int, char, či double. Napríklad funkcia cin pri načítaní do stringu číta znaky až pokým nenarazí na znak konca riadku, či na medzeru, takže funguje rovnako ako pri načítavaní čísel.

Tomuto typu dokonca nie je ani nutné povedať, ako veľký bude reťazec, ktorý do neho chceme vložiť. Pri načítaní zo vstupu sa totiž sám zväčší na potrebnú veľkosť.

Ak si nie sme istí alebo nevieme, akú veľkosť má naš string, teda koľko znakov v ňom je, tak môžme použiť jeho vlastnosť .size(). Tá nám vráti jeho veľkosť, teda číslo určujúce, koľko znakov sa v ňom nachádza.

Posledné vylepšenie je, že si vieme jednoducho vytvoriť pole takýchto stringov, teda v podstate dvojrozmerné pole charov a pristupovať k jednotlivým políčkam pomocou indexov rovnako, ako sme zvyknutí napríklad pri dvojrozmernom poli intov.

Nasledujúci príklad demonštruje, ako sa so stringom pracuje.

#include<iostream>
#include<vector>
#include<string>
//string sa nachadza v rovnomennej kniznici
using namespace std;
int main()
{
    //inicializacia stringu
    string ex1 = "text";
    string ex2;//prazdny string
    string ex3 = "ohodnotenie"; 
    cout << ex1 << endl;//vypisanie
    if(ex2.size() == 0)cout<<"Prazdny string."<<endl;
    cin >> ex2;//nacitanie
    
    //X.size() vracia dlzku stringu X
    cout << "String ktory si zadal ma dlzku " << ex2.size() << endl;
    
    //pristupovanie mozne na indexy v rozsahu 0 az X.size()-1
    for(int i = 3; i<ex3.size(); ++i)ex3[i] = 'a';
    
    //vypis po znakoch tiez nie je problematicky
    for(int i = 0; i<ex3.size(); ++i)cout<<ex3[i];
    cout<<endl;
    
    //vytvorenie vectoru stringov ? ziadny problem
    vector<string>dvojrozmerne(4);//vytvori vector velkosti 4
    
    dvojrozmerne[0] = "banan";
    dvojrozmerne[3] = "prask";
    
    cout << dvojrozmerne[0][3] << endl;//vypise konkretny znak, teda 'a'
    
    dvojrozmerne[3][4] = 'x';//upravime konkretny znak
    cout << dvojrozmerne[3] << endl;//vypise string prasx
    return 0;
}

Ak ste sa s týmto dátovým typom ešte nestretli, odporúčame vám sa s ním v tejto fáze pohrať a uistiť sa, že poznáte jeho základnú funkcionalitu. Keď už máme predstavu o tom, ako funguje string v C++, môžme sa postupne pustiť do jednotlivých sád.

Sada 1

Pre prvú sadu je hľadanie vcelku jednoduché, keďže osemsmerovka je tvorená iba jedným riadkom. To znamená, že sa v nej slovo môže nachádzať iba v dvoch smeroch.

Stačí preto nájsť dané slovo v nejakom texte, našej osemsmerovke. Text tvorí v tomto prípade iba jeden riadok, takže našou úlohou je napísať funkciu, ktorá nájde v jednom stringu nejaký iný. Tento problém sa zdá byť jednoduchý, ale v informatike je veľmi populárny a existuje naň množstvo rôznych algoritmov s odlišnými časovými zložitosťami.

My si však vystačíme s najjednoduchším postupom, ktorý nám napadne: Pre každú pozíciu skúsime, či sa na nej nemôže v texte začínať naše slovo. Ak sa prvé písmená zhodujú, pozrieme na ďaľšie písmeno v texte a porovnáme ho s ďaľším písmenom v našom hľadanom slove. Ak sa zhodujú, pokračujeme, pokým neprídeme na posledné písmeno. Ak sa na nejakom indexe nezhodujú, skončíme a začneme skúšať od ďalšieho začiatku.

Nasledovný program demonštruje kód funkcie, ktorá dostane na vstupe dva stringy a vypíše indexy prvého stringu, na ktorých začína výskyt druhého stringu. V programátorskom žargóne sa často prvý string nazýva text a druhý pattern alebo text a vzorka.

#include<iostream>
#include<string>
using namespace std;

void nachadza_sa(string& text, string& vzorka)
{
    for(int i=0;i<text.size();++i)
    {//pre každý index v texte
        
        if(i + vzorka.size() > text.size())return;
        //ak je dĺžka textu 10 a sme na 8 indexe, pattern
        //dlzky 4 uz urcite nenajdeme, lebo by koncil mimo textu
        
        for(int j=0;j < vzorka.size();++j)
        {
            if(text[i + j] != vzorka[j])break;
            //porovnovame pokym sa nelisi text od vzorky, vtedy skoncim
            if(j == vzorka.size()-1)cout<<"Vzorka najdena od "<<i<<endl;
            //ak som uz porovnal posledny prvok a neskoncil, tak mam zhodu 
            //na indexoch i az i + vzorka.size() - 1
        }
    }
}

int main()
{
    string text, vzorka;
    cin >> text >> vzorka;
    nachadza_sa(text, vzorka);
    return 0;
}

Toto isté nám už len stačí naimplementovať pre našu osemsmerovku. Rozdielom bude len to, že ak dané slovo niekde nájdeme, tak si políčka, na ktorých sa nachádzalo označíme za vyškrtnuté. Toto škrtanie spravíme v inom, pomocnom poli.

Musíme si ešte uvedomiť, že slovo môže ležať aj v opačnom smere ako zľava doprava. Ak sa slovo nachádza v osemsmerovke sprava doľava, použijeme malý trik. Predstavíme si naše slovo otočené naopak (prečítame ho odzadu). Uvedomme si, že v tomto prípade sa bude nachádzať v smere zľava doprava. A tak okrem hľadania každého slova budeme v osemsmerovke hľadať aj jeho otočenie (reverz). Ako príklad uvedieme hľadanie slova ba v texte kavab. Samotné slovo sa síce v texte nenachádza v smere zľava doprava, ale v opačnom smere áno. Keď si hladané slovo otočíme, dostaneme ab. Ten už v texte úspešne nájdeme. Ako domácu úlohu si rozmyslite, že tento postup bude fungovať v každom prípade.

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>//potrebne z dovodu reverse()

using namespace std;

int main()
{
    int r, s, n;
    string osemsmerovka, slovo, rev_slovo;
    cin >> r >> s >> n;
    cin >> osemsmerovka >> slovo;
    //načítame vstup
    
    rev_slovo = slovo;//skopirujeme slovo do pomocnej premennej
    reverse(rev_slovo.begin(), rev_slovo.end());
    //tato funkcia nam v linearnom case obrati string
    //v rev_slovo sa teraz nachadza povodne slovo obratene
    vector<bool>vyskrtnute(s, false);
    //na zaciatku nie je nic vyskrtnute
    bool najdene = false;
    int dlzka_slova;
    for(int i=0;i < s;++i)
    {
        dlzka_slova = slovo.size();
        
        for(int j=0;j < dlzka_slova;++j)
        {
            if(osemsmerovka[i+j] != slovo[j])break;
            if(j == dlzka_slova-1 )najdene = true;
        }
        
        for(int j=0;j < dlzka_slova;++j)
        {
            if(osemsmerovka[i+j] != rev_slovo[j])break;
            if(j == dlzka_slova-1 )najdene = true;
        }
            
        if(najdene)//ak sme nasli reverse alebo povodne slovo, zaznacime si
        {
            for(int j=0;j < dlzka_slova;++j)vyskrtnute[i+j] = true;
            break;
        }
    }
    
    for(int i=0;i < s;++i)
    {
        if(vyskrtnute[i] == false)
        {
            cout<<osemsmerovka[i];
            //ak nie je vyskrtnute... vypiseme
        }
    }
    cout<<endl;
    
    return 0;
}

Sada 2

Keď sme už dokázali napísať program riešiaci prvú sadu, stačí spraviť zopár zmien a budeme vedieť riešiť aj druhú sadu. Naše prvé riešenie prepíšeme na funkciu najdi(), ktorá nájde v texte zadané slovo a ak sa tam nachádza, vyškrtne ho podobne ako pri riešení prvej sady. Potom túto funkciu už len \(2n\)-krát zavoláme na nájdenie \(n\) slov a ich \(n\) reverzov.

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>

using namespace std;

vector<bool>vyskrtnute;

void najdi(string& osemsmerovka, string& slovo)
{
    bool najdene = false;
    int s = osemsmerovka.size(), dlzka_slova;
    for(int i=0;i < s;++i)
    {
        dlzka_slova = slovo.size();
        
        for(int j=0;j < dlzka_slova;++j)
        {
            if(osemsmerovka[i+j] != slovo[j])break;
            if(j == dlzka_slova-1 )najdene = true;
        }
            
        if(najdene)
        {
            for(int j=0;j < dlzka_slova;++j)vyskrtnute[i+j] = true;
            return;
        }
    }
}

int main()
{
    int r, s, n;
    string osemsmerovka, slovo, rev_slovo;
    cin >> r >> s >> n;
    cin >> osemsmerovka;
    
    vyskrtnute.resize(s, false);
    
    for(int i=0;i<n;++i)
    {
        cin >> slovo;
        rev_slovo = slovo;
        reverse(rev_slovo.begin(), rev_slovo.end());
        
        najdi(osemsmerovka, slovo);
        najdi(osemsmerovka, rev_slovo);
    }
    
    for(int i=0; i < s; ++i)
    {
        if(vyskrtnute[i] == false)
        {
            cout<<osemsmerovka[i];
        }
    }
    cout<<endl;
    
    return 0;
}

Sada 3, 4 a 5

Čo ak chceme ísť ďalej a vyriešiť osemsmerovku s viac riadkami? To čo si musíme uvedomiť je, že v tomto prípade sa môže hľadané slovo nachádzať vo všetkých ôsmych smeroch, s čím sme v prvých dvoch sadách nemuseli počítať.

Predstavme si, že chceme zistiť, či sa hľadané slovo začína na pozícii \((i,j)\). Najskôr si musíme zvoliť smer, v ktorom sa toto slovo bude v osemsmerovke nachádzať. Potom však musíme vedieť porovnať, či sa \(k\)-ty znak nášho slova rovná písmenku, ktoré je od pozícii \((i,j)\) v danom smere vzdialené na \(k\) krokov. Ako to však naimplementovať?

Pokúsme sa napísať jednoduchú funkciu, ktorej zadáme ako parametre súradnice začiatočného políčka, počet krokov a jeden zo smerov, v ktorom sa chceme pohnúť. Funkcia nám potom vypíše index políčka, na ktorom skončíme.

Na začiatok si jednotlivé smery očíslujeme. Smer nahor má číslo \(0\). Ostatné smery si očíslujeme v smere hodinových ručičiek, teda napr. smer doprava bude mať číslo \(2\), smer dole číslo \(4\) atď.

Ak si predstavíme, že sme začínali na pozícií \((i,j)\) a chceme vedieť nultý prvok (indexujeme od \(0\)) v nejakom smere, bude to vždy prvok \((i,j)\). Ak chceme vedieť prvý prvok v zadanom smere, vieme to zistiť vcelku jednoducho. Nech sme sa pohli na akékoľvek políčko vo vzdialenosti \(1\) od nášho pôvodného políčka \((i,j)\). Vieme, že jednotlivé indexy sa nám zmenia maximálne o \(1\). V prípade, že sme sa pohli jedným zo smerov nahor (\(0\), \(1\), \(7\)), tak od prvej súradnice odčítame \(1\) (inými slovami pričítame \(-1\)). Pretože index riadka sa zmenšil práve o jedna. Ak sme sa pohli jedným zo smerov (\(2\), \(6\)), je nám jasné, že prvá súradnica, teda index riadka, sa nijak nezmení – pričítame \(0\). A nakoniec, ak sme sa pohli do jedného zo smerov (\(3\), \(4\), \(5\)), tak k prvej súradnici \(1\) pričítame.

Rovnakú úvahu vieme urobiť aj pre druhú súradnicu kde pričítavame \(1\) ak sa hýbeme do smerov (\(1\), \(2\), \(3\)), nepričítavame nič pri smeroch (\(0\), \(4\)) a odčítavame \(1\) pri smeroch (\(5\), \(6\), \(7\)). Takže ak sa chceme z políčka \((i,j)\) pohnúť smerom 5, tak vieme, že sa dostaneme na políčko \((i+1,j-1)\).

Vytvorme si preto \(2\) pomocné polia zmena_x[] a zmena_y[] indexované smerom. Na \(l\)-tej pozícii poľa zmena_x[] bude dĺžka, o ktorú sa máme posunúť na riadku pri smere \(l\). Analogicky, pole zmena_y[] bude obsahovať na \(l\)-tej pozícií dĺžku, o ktorú sa musíme posunúť v stĺpci pri smere \(l\). Ak sme teda na pozícii \((i,j)\) a chceme sa pohnúť o jeden krok v smere \(smer\), indexy novej pozície budú \((i+zmena\_x[smer], j+zmena\_y[smer])\).

Všeobecnejšie, ak nás zaujíma kde sa nachádzame po \(k\) takýchto krokoch, stačí tieto dve čísla pričítať \(k\)-krát. Budeme sa teda nachádzať na políčku s indexom \((i+k \cdot zmena\_x[smer], j+k \cdot zmena\_y[smer])\).

Nasleduje implementácia požadovanej funkcie. Môžete si v nej pozrieť, čo presne obsahujú polia zmena_x[] a zmena_y[] a porovnať ich s predchádzajúcim obrázkom.

#include<iostream>
#include<vector>
#include<string>

using namespace std;

int zmena_x[]={-1, -1, 0, 1, 1, 1, 0, -1};
int zmena_y[]={0, 1, 1, 1, 0, -1, -1, -1};

void kde_skoncim(int i, int j, int pocet_krokov, int smer)
{
    int nove_i, nove_j;
    nove_i = i + pocet_krokov * zmena_x[smer];
    nove_j = j + pocet_krokov * zmena_y[smer];
    cout<< "Suradnice su: " << nove_i << ";" << nove_j <<endl;
}

int main()
{
    int i, j, pocet_krokov, smer;
    cin >> i >> j >> pocet_krokov >> smer;
    kde_skoncim(i, j, pocet_krokov, smer);
    return 0;
}

V tomto momente máme už všetko, čo potrebujeme na to, aby sme napísali novú verziu našej funkcie najdi(), ktorá si poradí aj so zložitejšími osemsmerovkami.

V tejto funkcii si pre všetky pozície v osemsmerovke a všetkých osem smerov overíme, či sa v danom smere nenachádza hľadané slovo. Ak áno, vyškrtáme ho a prejdeme na ďaľšie slovo. Takto už vieme riešiť všetky ostatné sady a dostávame aj vzorové riešenie. Maličkosťou je, že dobrým zvykom je polia zmena_x[] a zmena_y[] označovať dx[], resp. dy[]. Vyhnete sa tým zbytočnému písaniu a budete používať rovnakú konvenciu.

#include<iostream>
#include<vector>
#include<string>

using namespace std;

int dx[] = {-1, -1, 0, 1, 1, 1, 0, -1};
int dy[] = {0, 1, 1, 1, 0, -1, -1, -1};

vector<vector<bool> >vyskrtnute;
//tu si pamatam co este nemam vyskrtnute

void najdi(vector<string>&osemsmerovka, string &hladane)//funkcia najdi vyskrtne slovo "hladane"
{
    int r = osemsmerovka.size(), s = osemsmerovka[0].size(), akt_x, akt_y;
    //r, s su rozmery osemsmerovky
    
    for(int i=0;i<r;++i)for(int j=0;j<s;++j)//pre vsetky indexy
    {
                for(int k=0;k<8;++k)//pre vsetky smery
                {
                    for(int d=0;d<hladane.size();++d)//prechadzam slovo kym mam zhodu
                    {
                        //vypocitam si, kde momentalne som
                        akt_x=i+d*dx[k];
                        akt_y=j+d*dy[k];
                        
                        if(akt_x >= 0 && akt_y >= 0 && akt_x<r && akt_y < s && osemsmerovka[akt_x][akt_y] == hladane[d]);
                        else break;//ak som von zo svojho pola alebo nemam zhodu na d-tom indexe v slove tak koncim
                        if(d == hladane.size()-1)//ak som dosiel az na koniec slova, tak ho uz len vyskrtnem a skoncim
                        {
                            for(int dd=0;dd<hladane.size();++dd)
                            {
                                akt_x=i+dd*dx[k];
                                akt_y=j+dd*dy[k];
                                vyskrtnute[akt_x][akt_y]=true;
                            }
                            return;
                        }
                    
                    }
                }
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    string hladane;
    int r, s, n;
    cin >> r >> s >> n;
    
    vector<string>osem(r);
    vyskrtnute.resize(r, vector<bool>(s, false));
    
    for(int i=0;i<r;++i) cin >> osem[i];
    
    for(int f=0;f<n;++f)
    {
        cin >> hladane;
        najdi(osem, hladane);
    }
    
    for(int i=0;i<r;++i)for(int j=0;j<s;++j)
    {
        if(!vyskrtnute[i][j])cout<<osem[i][j];
    }
    cout<<endl;
    return 0;
}

Čo sa týka časovej a pamäťovej zložitosti, pri hľadaní slova sa nám v najhoršom prípade môže stať, že v každom smere sa písmená na mriežke líšia od nášho slova až v poslednom znaku. Pri tomto procese spravíme \(8 \cdot |slovo|\) porovnaní, kde \(|slovo|\) je počet znakov slova. Slovo v najhoršom prípade budeme výhľadávať z každej pozície mriežky, teda z \(r \cdot s\) pozícií. Pre jedno slovo teda dostávame približne \(r \cdot s \cdot 8 \cdot |slovo|\) krokov.

Pretože pri O-notácii zanedbávame konštanty, môžeme beztrestne vyškrtnúť \(8\) a dostaneme časovú zložitosť vyhľadávania jedného slova \(O(r \cdot s \cdot |slovo|)\). Slov je ale na vstupe \(n\) a spravíme preto rádovo \(r \cdot s \cdot |slovo_1| + r \cdot s \cdot |slovo_2| + ... + r \cdot s \cdot |slovo_n|\) krokov. Všimnime si, že \(r\cdots\) môžeme z výrazu vynať a dostaneme tak \(r \cdot s \cdot (|slovo_1| + |slovo_2| + ... + |slovo_n|)\). Súčet \(|slovo_1| + |slovo_2| + ... + |slovo_n|\) je rovný celkovému súčtu slov. Celkovo preto dostávame časovú zložitosť \(O(r\cdot s\cdot sucet\_dlzok\_slov)\).

Pamäťová zložitosť je \(O(r \cdot s + sucet\_dlzok\_slov)\), kedže si musíme pamätať údaje pre mriežku a slová na vstupe.