26. PUŽ – REŠENJE ZADATKA

Tekst zadatka:


/*
Nemanja ima 6 godina i počeo je da uči da čita i piše. Od strica je dobio vežbanku za učenje slova u kojoj se nalazi vežbica "Puž".
Naime u ovoj vežbici postoji tabela dimenzija n x m u koju je potrebno upisati neku rečenicu na sledeći način:
kreće se iz gornjeg levog ugla tabele i upisuju se slova ka desnoj ivici tabele dokle može. Kada se stigne do ivice onda se nastavlja
upisivanje na dole do ivice, zatim na desno do ivice, pa na gore dok ima mesta, onda opet na desno i tako dok se ne popuni cela tabela (slika).
U tabelu se upisuju samo slova, ignorišu se razmaci, znakovi interpunkcije i slično.
Pošto je Nemanja suviše mali za ovu vežbu, tabelu je popunio stric.
Nemanju sada zanima da li se u rečenici koja je korišćena da se popuni tabela nalazi ime njegovog omiljenog superheroja.
Pošto Nemanja još ne zna sva slova, pomozite mu da ovo otkrije.

Ulaz
U prvom redu standardnog ulaza se nalaze dva cela broja n i m (2 ≤ n, m ≤ 50)
koja redom predstavljaju broj redova i broj kolona ove tabele.
U narednih n redova se nalazi po m karaktera (mala slova engleske abecede)
koji svi zajedno predstavljaju popunjenu tabelu.
U narednom redu se nalazi niska karaktera (dužine do 30) koja predstavlja ime
Nemanjinog omiljenog superheroja (takođe mala slova engleske abecede, bez razmaka i znakova interpunkcije).

Izlaz
U jedinom redu standardnog izlaza ispisati jedan ceo broj koji predstavlja
poziciju u rečenici od koje počinje ime traženog superheroja.
U slučaju da ime ne postoji, ispisati -1.
Ukoliko se ime pojavljuje više puta, ispisati početnu poziciju prvog pojavljivanja.

se ne pojavljuje jer je njeno ime u rečenici u padežu (akuzativu).
*/

Primer 1


Ulaz
4 5
mnogo
jdrmv
aaneo
psmil
spajdrmen

Izlaz
11

Objašnjenje
Kada se tabela razvije, dobija se niska karaktera mnogovolimspajdrmena,
tako da se reč spajdrmen pojavljuje počevši od 11. mesta.

Primer 2


Ulaz
5 5
dalis
rnuui
ccudt
oivoi
adelg
crnaudovica

Izlaz
-1

Objašnjenje
Iako se u rečenici priča o Crnoj udovici, niz karaktera crnaudovica
se ne pojavljuje jer je njeno ime u rečenici u padežu (akuzativu).

Rešenje

Prvo se učitava ceo tekst kao matrica polja gde se u svakom polju smešta određeni karakter. Matrica je ovde zapravo vektor string podataka, gde svaki string predstavlja jedan red tabele. Zatim se učita i reč koja se pretražuje. Pretraga se vrši linearno i pretražuje se jedan niz koji sadrži ceo tekst, ali se popunjava pravcem koji je prikazan na slici. Promena pravca se vrši kroz do-while petlju, a unutrašnja for petlja služi da se prolazi kroz tekući red ili kolonu i to u smeru koji odgovara tekućem pravcu kretanja. Pravac se menja posle završene unutrašnje petlje, a analizira se pomoću switch naredbe.


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

using namespace std;

int main()
{
    int m, n;
    cin >> n >> m; // Učitavamo dimenzije matrice: n redova i m kolona

    string superheroj;
    vector<string> tabela(n);

    // Učitava tekst red po red, gde je tabela[i] red teksta
    for (int i = 0; i < n; i++)
        cin >> tabela[i];

    cin >> superheroj; // Učitava reč koju tražimo u spirali

    // Inicijalizacija promenljivih za kretanje kroz matricu
    int tekuciRed = 0;      // Trenutni red za kretanje horizontalno
    int tekucaKol = m - 1;  // Trenutna kolona za kretanje vertikalno
    int pocR = 0;            // Početni red za trenutnu spiralu
    int krajR = n - 1;       // Krajnji red za trenutnu spiralu
    int pocK = 0;            // Početna kolona za trenutnu spiralu
    int krajK = m - 1;       // Krajnja kolona za trenutnu spiralu
    int pravac = 1;          // Trenutni pravac kretanja: 1-desno, 2-dole, 3-levo, 4-gore
    string text = "";        // Niz karaktera u obliku puža
    int pos = -1;            // Pozicija početka reči superheroja

    // Glavna petlja za kretanje kroz matricu u obliku puža
    do {
        switch (pravac) // Analiziramo trenutni pravac
        {
        case 1: // Desno
            for (int i = pocK; i <= krajK; i++)
                text += tabela[tekuciRed][i]; // Dodajemo karaktere iz reda
            pocR++;               // Pomak početnog reda nadole
            tekuciRed = krajR;    // Priprema za sledeći vertikalni pravac
            break;

        case 2: // Dole
            for (int i = pocR; i <= krajR; i++)
                text += tabela[i][tekucaKol]; // Dodajemo karaktere iz kolone
            krajK--;              // Smanjujemo krajnju kolonu ulevo
            tekucaKol = pocK;     // Priprema za sledeći horizontalni pravac
            break;

        case 3: // Levo
            for (int i = krajK; i >= pocK; i--)
                text += tabela[tekuciRed][i]; // Dodajemo karaktere iz reda unazad
            krajR--;              // Smanjujemo krajnji red nagore
            tekuciRed = pocR;     // Priprema za sledeći vertikalni pravac
            break;

        case 4: // Gore
            for (int i = krajR; i >= pocR; i--)
                text += tabela[i][tekucaKol]; // Dodajemo karaktere iz kolone unazad
            pocK++;               // Pomak početne kolone udesno
            tekucaKol = krajK;    // Priprema za sledeći horizontalni pravac
            break;
        }

        // Menjanje pravca u smeru kazaljke na satu
        pravac++;
        pravac %= 4; // Održavamo pravac u opsegu 1-4
        if (pravac == 0) pravac = 4;

    } while (krajK >= pocK && krajR >= pocR); // Dok spirala nije završena

    // Traži poziciju superheroja u dobijenom nizu karaktera
    pos = text.find(superheroj);

    if (pos != -1)
        cout << pos + 1 << endl; // Ispisujemo 1-baziranu poziciju
    else
        cout << pos << endl;     // Ako ne postoji, ispisujemo -1

    return 0;
}

Ovaj zadatak zahteva da simuliramo kretanje puža kroz matricu, odnosno n × m tabelu, kako bismo kreirali niz karaktera bez znakova interpunkcije i razmaka. Zadatak se rešava tako što pratimo kretanje puža u četiri pravca: desno, dole, levo i gore, koristeći promenljive koje upravljaju početkom i krajem redova i kolona. Na kraju, pretražujemo dobijeni niz karaktera kako bismo pronašli poziciju Nemanjinog omiljenog superheroja. Program koristi funkciju find() za pretragu podstringa, a rezultat se ispisuje u skladu sa zadatim pravilima.

Komentar i analiza rešenja

Rešenje je tačno i funkcionalno, jer pravilno simulira spiralu (puža) kroz matricu i ispravno pronalazi poziciju zadatog imena. Struktura koda je jasna i koristi razumljivu logiku promene pravaca pomoću switch naredbe i ciklusa do-while. Efikasnost rešenja je zadovoljavajuća za ograničenja zadatka (do 50×50 elemenata), jer kompleksnost ostaje O(n·m) za formiranje niza i O(k) za pretragu podstringa. Moguća poboljšanja uključuju:

Preciznije imenovanje promenljivih (npr. redPocetak, kolonaKraj) radi bolje čitljivosti.
Uklanjanje manjih nelogičnosti u komentarima (npr. opisi pomeranja redova i kolona).
Dodavanje funkcije za generisanje spiralnog niza radi modularnosti koda.
Moguća optimizacija: pretraga dok se spiralni niz gradi, kako bi se izbeglo skladištenje celog niza odjednom.

Uprkos tim sitnim poboljšanjima, implementacija je sasvim dobra i daje tačan rezultat, pa se može smatrati korektnim i dovoljno efikasnim rešenjem zadatka.

Rešenje 2 - Pruž (spiralno) i pretraga imena superheroja

Rešenje ovog zadatka zahteva rekonstrukciju rečenice iz zadate matrice dimenzija n×m tako što se kreće u obliku puža (spiralno), te zatim proveru da li unutar te rečenice postoji ime superheroja. Postupak rešavanja uključuje sledeće korake:

Rekonstruišite rečenicu iz matrice u "puž" obliku.
Izbacite sve nebitne znakove i razmake (ako je potrebno).
Pronađite poziciju prvog pojavljivanja imena superheroja u rečenici (ako postoji).
Ispišite rezultat.

Kod:


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

using namespace std;

// Funkcija koja vraća niz karaktera u spirali iz matrice
vector<char> spirala(vector<vector<char>>& matrica, int redovi, int kolone) {
    vector<char> rezultat;

    // Inicijalizacija granica matrice
    int gornja = 0, donja = redovi - 1;
    int leva = 0, desna = kolone - 1;

    // Nastavljamo dok se granice ne preklapaju
    while (gornja <= donja && leva <= desna) {
        // Krećemo se s leva na desno po gornjem redu
        for (int i = leva; i <= desna; i++) {
            rezultat.push_back(matrica[gornja][i]);
        }
        gornja++; // Pomera gornju granicu nadole

        // Krećemo se s gore na dole po desnoj koloni
        for (int i = gornja; i <= donja; i++) {
            rezultat.push_back(matrica[i][desna]);
        }
        desna--; // Smanjuje desnu granicu ulevo

        // Krećemo se s desna na levo po donjem redu, ako još ima preostalih redova
        if (gornja <= donja) {
            for (int i = desna; i >= leva; i--) {
                rezultat.push_back(matrica[donja][i]);
            }
            donja--; // Pomeramo donju granicu nagore
        }

        // Krećemo se s dole na gore po levoj koloni, ako još ima preostalih kolona
        if (leva <= desna) {
            for (int i = donja; i >= gornja; i--) {
                rezultat.push_back(matrica[i][leva]);
            }
            leva++; // Pomeramo levu granicu udesno
        }
    }

    return rezultat; // Vraćamo rekonstruisanu rečenicu
}

int main() {
    int redovi, kolone;
    cin >> redovi >> kolone; // Učitavamo dimenzije matrice

    // Učitavamo matricu karaktera red po red
    vector<vector<char>> matrica(redovi, vector<char>(kolone));
    for (int i = 0; i < redovi; i++) {
        for (int j = 0; j < kolone; j++) {
            cin >> matrica[i][j]; // Učitavamo svaki karakter
        }
    }

    string superheroj;
    cin >> superheroj; // Učitavamo ime superheroja

    // Kreiramo niz karaktera u spirali pomoću funkcije spirala
    vector<char> recenica = spirala(matrica, redovi, kolone);
    string kreirana_recenica(recenica.begin(), recenica.end());

    // Tražimo poziciju imena superheroja u rekonstruisanoj rečenici
    size_t pronadjeno = kreirana_recenica.find(superheroj);
    
    if (pronadjeno != string::npos) {
        cout << pronadjeno + 1 << endl; // Ispisujemo 1-baziranu poziciju
    } else {
        cout << -1 << endl; // Ako reč ne postoji, ispisujemo -1
    }

    return 0;
}

Komentar na rešenje:

Ova varijanta je efikasna jer koristi standardni algoritam za "spiralno" prolazak kroz matricu, poznat kao "puž". Funkcija spirala elegantno obrađuje granice matrice i dodaje karaktere u rezultat redom prolaska. Svaki korak je detaljno komentarisano kako bi se jasno razumela logika pomeranja granica.

Pretraga imena superheroja se vrši direktno nad rekonstruisanom rečenicom koristeći standardnu funkciju find. Program ispravno vraća poziciju prvog pojavljivanja, ili -1 ako reč nije prisutna.

Prednosti ovog pristupa:

Čitljiv i modularan kod zahvaljujući funkciji spirala.
Jasno definisane granice i pravci kretanja kroz matricu.
Efikasnost dovoljna za standardne dimenzije matrice (do 50×50).

Moguća poboljšanja:

Automatsko filtriranje nepotrebnih znakova pre pretrage (npr. razmaci, interpunkcija).
Ispis svih pozicija gde se superheroj pojavljuje.
Optimizacija memorijskog korišćenja ako je matrica veoma velika.
Dodavanje provere validnosti unosa i dimenzija matrice.

Rešenje 3 - Puž (rekurzija / backtracking, efikasno)

Ova varijanta koristi rekurziju da bi se spiralno pročitala matrica i odmah se traži ime superheroja unutar rečenice. Na taj način se efikasno prekida pretraga čim se nađe traženi niz karaktera. Ovaj pristup smanjuje memorijsku potrošnju i omogućava brže pronalaženje prvog pojavljivanja.

Koraci rešenja:

Rekurzivno čitajte matricu u "puž" obrascu, dodajući karaktere u string dokle god ne naiđete na kraj ili dok ne pronađete superheroj.
Za svaki dodani karakter proverite da li se niz završava traženim imenom superheroja.
Ako se ime pronađe, zabeležite poziciju i prekinite dalju pretragu.
Ako se ime ne pronađe nakon prolaska kroz celu matricu, ispisuje se -1.

Kod:


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

using namespace std;

int n, m;
vector<vector<char>> matrica;
string superhero;
int found_pos = -1;

// Funkcija koja rekurzivno prolazi kroz matricu u spiralnom obliku
void spiralaDFS(int g, int d, int l, int r, string trenutna) {
    if (found_pos != -1) return; // prekid ako je već pronađeno

    // Pomeramo se desno
    for (int i = l; i <= r; i++) {
        trenutna.push_back(matrica[g][i]);
        if (trenutna.size() >= superhero.size() && trenutna.substr(trenutna.size() - superhero.size()) == superhero) {
            found_pos = trenutna.size() - superhero.size() + 1; // 1-bazirano
            return;
        }
    }
    g++;

    // Pomeramo se dole
    for (int i = g; i <= d; i++) {
        trenutna.push_back(matrica[i][r]);
        if (trenutna.size() >= superhero.size() && trenutna.substr(trenutna.size() - superhero.size()) == superhero) {
            found_pos = trenutna.size() - superhero.size() + 1;
            return;
        }
    }
    r--;

    // Pomeramo se levo
    if (g <= d) {
        for (int i = r; i >= l; i--) {
            trenutna.push_back(matrica[d][i]);
            if (trenutna.size() >= superhero.size() && trenutna.substr(trenutna.size() - superhero.size()) == superhero) {
                found_pos = trenutna.size() - superhero.size() + 1;
                return;
            }
        }
        d--;
    }

    // Pomeramo se gore
    if (l <= r) {
        for (int i = d; i >= g; i--) {
            trenutna.push_back(matrica[i][l]);
            if (trenutna.size() >= superhero.size() && trenutna.substr(trenutna.size() - superhero.size()) == superhero) {
                found_pos = trenutna.size() - superhero.size() + 1;
                return;
            }
        }
        l++;
    }

    // Rekurzivno pozivamo za unutrašnju spiralu
    if (g <= d && l <= r) spiralaDFS(g, d, l, r, trenutna);
}

int main() {
    cin >> n >> m;
    matrica.resize(n, vector<char>(m));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> matrica[i][j];
        }
    }

    cin >> superhero;

    spiralaDFS(0, n-1, 0, m-1, "");

    cout << found_pos << endl;

    return 0;
}

Komentar na rešenje:

Ovaj pristup koristi rekurziju za čitanje matrice u spiralnom obliku i istovremeno proverava prisustvo imena superheroja. Prednost je što se pretraga prekida čim se pronađe traženi niz, što čini algoritam efikasnijim u odnosu na prethodnu varijantu koja prvo čita celu matricu, pa tek onda traži ime.

Ova verzija je posebno pogodna za veće matrice i duže nizove, jer smanjuje memorijsku potrošnju i vreme izvršenja. Lako se može proširiti za dodatne zahteve kao što su ignorisanje nebitnih karaktera ili pretraga svih pojavljivanja.