ZADATAK ZRAK — REŠENJE

Tekst zadatka

Poznato je da radio-talasima smetaju prepreke koje im se nađu na putu. Potrebno je istražiti da li radio-talasi mogu da prođu kroz pravougaonu oblast u kojoj je zasađeno drveće.

Radio-talas se ispušta iz gornjeg levog ugla te oblasti i to u pravcu koji je određen vertikalnim i horizontalnim pomerajem. To su brojevi koji određuju razliku između koordinata narednog i tekućeg polja koje je zrak dostigao.

Na primer, ako su pomeraji redom 2 i 1, to znači da se zrak u svakom koraku pomeri za dve vrste naniže i jednu kolonu nadesno. Tada redom prelazi polja čije su koordinate (0,0), (2,1), (4,2), itd.

Napisati program koji određuje koliko stabala će se naći na putu radio-talasa.

Ulaz

Prva linija standardnog ulaza sadrži dimenzije matrice bv i bk (3 ≤ bv,bk ≤ 100), razdvojene razmakom.

Nakon toga se nalazi opis matrice, pri čemu su polja koja sadrže stabla označena sa 1, a polja koja ne sadrže stabla sa 0.

Na kraju se nalazi linija u kojoj su dati pomeraji: vertikalni pomeraj pv i horizontalni pomeraj pk. Pomeraji su prirodni brojevi i razdvojeni su razmakom.

Izlaz

Na standardni izlaz ispisati broj stabala koje radio-signal poseti.

Osnovna ideja rešenja

Oblast u kojoj se nalaze stabla predstavljena je matricom. Svako polje matrice ima dve koordinate: broj vrste i broj kolone.

Pošto signal počinje iz gornjeg levog ugla, njegova početna pozicija je (0,0).

Ako su pomeraji pv i pk, svako sledeće polje dobijamo tako što na trenutne koordinate dodamo te vrednosti:

v = v + pv
k = k + pk

Na svakoj posećenoj poziciji proveravamo vrednost u matrici. Ako je ona jednaka 1, na tom polju se nalazi stablo i povećavamo brojač za jedan.

Kretanje se nastavlja sve dok se koordinate nalaze unutar granica matrice. Čim signal izađe van matrice, petlja se završava.

Važna stvar — proverava se i početno polje

Signal počinje u polju (0,0), pa i to polje predstavlja posećeno polje i mora biti provereno.

Zbog toga se provera matrice nalazi na početku petlje, a tek nakon toga se prelazi na sledeću poziciju.

Na primer, za pomeraje 2 1, signal obilazi:

(0,0) → (2,1) → (4,2) → (6,3) → (8,4)

Poslednja pozicija (8,4) više nije u matrici dimenzije 8 × 8, jer vrste imaju indekse od 0 do 7. Zato se na toj poziciji signal više ne proverava.

Ideja algoritma

1. Učitati broj vrsta bv i broj kolona bk.
2. Učitati sva polja matrice i smestiti ih u dvodimenzionalni vektor.
3. Učitati vertikalni i horizontalni pomeraj pv i pk.
4. Postaviti početne koordinate na v = 0 i k = 0.
5. Dok se signal nalazi unutar matrice, proveriti da li se na trenutnoj poziciji nalazi stablo.
6. Ako je vrednost jednaka 1, povećati brojač.
7. Pomeri se za pv vrsta i pk kolona.
8. Po izlasku iz matrice ispisati broj pronađenih stabala.

Kompletno C++ rešenje

// ZADATAK ZRAK - REŠENJE
// Rešenje pomoću dvodimenzionalnog vektora

#include <iostream>
#include <vector>

using namespace std;

int main()
{
    int bv, bk, in;
    int pv, pk;

    // bv - broj vrsta matrice
    // bk - broj kolona matrice
    // pv - vertikalni pomeraj
    // pk - horizontalni pomeraj

    vector<vector<int>> stabla;

    // Učitavamo dimenzije matrice.
    cin >> bv >> bk;

    // Učitavamo matricu.
    // Svaki red prvo formiramo kao poseban vektor,
    // a zatim taj red dodajemo u dvodimenzionalni vektor.
    for (int i = 0; i < bv; i++)
    {
        vector<int> red;

        for (int j = 0; j < bk; j++)
        {
            cin >> in;

            // Dodajemo učitanu vrednost u trenutni red.
            red.push_back(in);
        }

        // Dodajemo formirani red u matricu.
        stabla.push_back(red);
    }

    // Učitavamo pomeraj po vrsti i po koloni.
    cin >> pv >> pk;

    // Signal počinje u gornjem levom uglu,
    // odnosno na koordinatama (0,0).
    int v = 0;
    int k = 0;

    // b predstavlja broj posećenih stabala.
    int b = 0;

    // Petlja traje dok se signal nalazi unutar matrice.
    while (v < bv && k < bk)
    {
        // Ako je vrednost na trenutnoj poziciji 1,
        // na tom polju se nalazi stablo.
        if (stabla[v][k] == 1)
        {
            b++;
        }

        // Prelazimo na sledeću poziciju radio-talasa.
        v += pv;
        k += pk;
    }

    // Ispisujemo ukupan broj posećenih stabala.
    cout << b << endl;

    return 0;
}

Objašnjenje koda

1. Zaglavlja programa
Zaglavlje <iostream> omogućava korišćenje standardnog ulaza i izlaza, odnosno naredbi cin i cout.

Zaglavlje <vector> omogućava korišćenje kontejnera vector, koji ćemo koristiti za čuvanje matrice.

2. Čuvanje matrice
Promenljiva stabla je dvodimenzionalni vektor: vector<vector<int>>.

Spoljašnji vektor sadrži redove matrice, dok svaki unutrašnji vektor predstavlja jedan red.

Na primer:

vector<vector<int>> stabla;

omogućava da matricu posmatramo na isti način kao i klasičnu dvodimenzionalnu matricu, pa elementu pristupamo pomoću stabla[v][k].

3. Učitavanje matrice
Za učitavanje matrice koriste se ugnježdene petlje. Spoljašnja petlja prolazi kroz vrste, a unutrašnja kroz kolone.

for (int i = 0; i < bv; i++)
{
    vector<int> red;

    for (int j = 0; j < bk; j++)
    {
        cin >> in;
        red.push_back(in);
    }

    stabla.push_back(red);
}

Na ovaj način se učitava jedno po jedno polje matrice. Kada se učita ceo red, on se dodaje u vektor stabla.

4. Početna pozicija radio-talasa
Signal se emituje iz gornjeg levog ugla matrice, pa su početne koordinate:

int v = 0;
int k = 0;

Promenljiva v predstavlja broj vrste, a k broj kolone.

5. Provera da li smo unutar matrice
Uslov:

while (v < bv && k < bk)

znači da se telo petlje izvršava samo dok su trenutna vrsta i trenutna kolona unutar matrice.

Pošto su pomeraji prirodni brojevi, koordinate se povećavaju, pa nije potrebno posebno proveravati slučajeve v < 0 i k < 0.

6. Provera stabla
Na trenutnoj poziciji proveravamo vrednost matrice:

if (stabla[v][k] == 1)
{
    b++;
}

Ako je vrednost 1, na tom polju se nalazi stablo i promenljiva b se povećava za jedan.

7. Prelaz na sledeće polje
Nakon provere trenutnog polja, signal prelazi na sledeću poziciju:

v += pv;
k += pk;

To je isto što i:

v = v + pv;
k = k + pk;

Na taj način se u svakom koraku pomeramo za isti broj vrsta i isti broj kolona.

8. Završetak algoritma
Kada signal sledećim pomeranjem izađe iz matrice, uslov while više nije ispunjen i petlja se završava.

Tada promenljiva b sadrži upravo ukupan broj stabala preko kojih je signal prošao, pa se ona ispisuje:

cout << b << endl;

Praćenje algoritma na primeru

Posmatrajmo prvi primer, u kome su pomeraji:

pv = 2
pk = 1

Signal počinje na poziciji (0,0). Nakon svakog koraka dodajemo 2 na koordinatu vrste i 1 na koordinatu kolone.

Dobijamo sledeće pozicije:

(0,0)
(2,1)
(4,2)
(6,3)
(8,4)   ← izlazak iz matrice

Za matricu iz primera vrednosti na tim posećenim poljima su:

(0,0) = 0
(2,1) = 0
(4,2) = 1
(6,3) = 1

Dakle, signal je posetio dva stabla, na pozicijama (4,2) i (6,3).

Zbog toga je rezultat:

2

Praćenje drugog primera

U drugom primeru pomeraji su:

1 2

Zato signal obilazi pozicije:

(0,0)
(1,2)
(2,4)
(3,6)
(4,8)   ← izlazak iz matrice

Na pozicijama (0,0) i (2,4) nalaze se stabla, pa je ukupan broj posećenih stabala jednak 2.

Zašto koristimo dvodimenzionalni vektor?

Matrica je prirodan način predstavljanja problema zato što imamo pravougaonu oblast podeljenu na vrste i kolone.

Dvodimenzionalni vektor omogućava da podatke čuvamo tako da se svako polje može jednostavno pronaći pomoću njegovih koordinata:

stabla[v][k]

Ovde je v broj vrste, a k broj kolone. To odgovara načinu na koji su koordinate zadate u tekstu zadatka.

Vremenska složenost

Učitavanje matrice zahteva O(bv · bk) operacija, jer moramo da učitamo svako polje matrice.

Kretanje radio-talasa zahteva samo obilazak polja koja se nalaze na njegovom putu. Pošto se za svaki korak koordinate povećavaju za unapred poznate pomeraje, broj tih koraka je mali u odnosu na celu matricu.

Ukupna vremenska složenost je zato: O(bv · bk).

Memorijska složenost je takođe: O(bv · bk), jer se cela matrica čuva u memoriji.

Česte greške

1. Zaboravljanje početnog polja
Polje (0,0) je deo putanje radio-talasa i mora biti provereno. Nije pravilno prvo pomeriti signal, pa tek onda proveravati matricu.

2. Obrtanje pomeraja
Prvi broj predstavlja pomeraj po vrsti, a drugi po koloni:

v += pv;
k += pk;

Ne treba ih zameniti.

3. Pristup matrici van njenih granica
Pre korišćenja izraza stabla[v][k] mora se proveriti da li su v i k dozvoljene koordinate.

4. Nepotrebna provera negativnih koordinata
U ovom zadatku su pomeraji prirodni brojevi, pa se signal kreće samo naniže i nadesno. Zbog toga koordinate ne mogu postati negativne.

Sažetak rešenja

Rešenje se zasniva na jednostavnom praćenju putanje radio-talasa kroz matricu. Počinjemo od (0,0), proveravamo da li se na tom polju nalazi stablo, a zatim u svakom koraku dodajemo zadate pomeraje na koordinatu vrste i koordinatu kolone.

Kada signal izađe iz matrice, proces se završava. Brojač koji smo povećavali svaki put kada naiđemo na vrednost 1 predstavlja konačan broj stabala koje je radio-signal posetio.

---

Povratak
|< Kvalifikacije za okružna takmičenja

---