Web Analytics Made Easy - Statcounter
SVET PROGRAMIRANJA

BEKTREKING I GRUBA SILA- PRIMERI

Brute Force (gruba sila)

Brute force je najjednostavniji način rešavanja problema: pokušavamo sve moguće opcije ili kombinacije dok ne pronađemo rešenje. To je kao da koristimo silu da obavimo posao – ne pokušavamo nijedan specifičan pametni trik, nego testiramo svaki mogući put. Ovakav pristup je lak za razumevanje i programiranje, jer ne zahteva komplikovane algoritamske tehnike. Brute force koristimo kada imamo mali broj mogućih rešenja ili kada nam nije važna brzina programa. Na primer, ako imamo samo nekoliko mogućih kombinacija, možemo proveriti svaku od njih.

Međutim, kod većih problema brute force može postati veoma spor. Broj mogućih kombinacija brzo raste kako se veličina problema povećava, pa isprobavanje svake opcije postaje neefikasno. Brute force tada troši mnogo vremena na nepotrebne provere.

Karakteristike brute force metode:

  • Proverava sve moguće kombinacije (ili rezultate) jednog problema.
  • Jednostavna je za razumevanje i implementaciju.
  • Dobro radi za mali broj kombinacija, ali postaje neučinkovita za veće probleme.

Primer brute force (C++)

Na primer, da pronađemo sve parove brojeva u nizu čiji zbir je jednak određenoj vrednosti (target), možemo koristiti brute force:

int arr[] = {1, 2, 3, 4};
int n = 4;
int target = 5;
// find pairs whose sum equals target
for (int i = 0; i < n; i++) {
    for (int j = i+1; j < n; j++) {
        if (arr[i] + arr[j] == target) {
            cout << arr[i] << " + " << arr[j] << " = " << target << endl;
        }
    }
}

Backtracking

Backtracking je naprednija metoda pretrage rešenja koja gradi moguća rešenja korak po korak. Ideja je da u svakom koraku biramo jedan element i rekurzivno nastavimo dalje. Ako u nekom trenutku shvatimo da trenutna kombinacija ne može da dovede do rešenja (npr. neki uslov nije zadovoljen), pravimo korak unazad i menjamo izbor. Na taj način izbacujemo čitave grane pretrage za koje znamo da neće dati rešenje. Ovo znatno smanjuje broj provera u odnosu na običnu brute force pretragu.

Backtracking se često koristi kod kombinatornih problema ili slagalica sa dodatnim uslovima (npr. Sudoku, N-queens). Omogućava da brzo odbacimo nepotrebne puteve i da efikasno nađemo sva rešenja. Mana je što implementacija zahteva rekurziju i može biti složenija od prostog brute force pristupa, ali značajno ubrzava pretragu kod problema sa velikim brojem mogućnosti.

Karakteristike backtracking metode:

  • Koristi rekurziju i vraćanje koraka (backtracking) kada neka kombinacija ne daje rešenje.
  • Odbacuje nepotrebne puteve kako bi bila efikasnija.
  • Efikasniji je od čistog brute force-a kod problema sa mnogo kombinacija, ali je kod složeniji za pisanje.

Primer backtracking (C++)

Jednostavan primer backtracking-a je generisanje svih podskupova skupa brojeva:

vector arr = {1, 2, 3};
vector current;
generateSubsets(0, arr, current);  // start recursion

void generateSubsets(int idx, vector& arr, vector& current) {
    if (idx == arr.size()) {
        for (int x : current)
            cout << x << " ";
        cout << endl;
        return;
    }
    // skip arr[idx]
    generateSubsets(idx + 1, arr, current);
    // take arr[idx]
    current.push_back(arr[idx]);
    generateSubsets(idx + 1, arr, current);
    current.pop_back();
}

Brute Force vs Backtracking

I brute force i backtracking služe za pretragu svih mogućih kombinacija rešenja, ali to rade na različite načine. Brute force doslovno isprobava svaki mogući slučaj bez ikakve optimizacije. To ga čini najjednostavnijim za implementaciju, ali brzo gubi efikasnost kada se broj kombinacija poveća. Nasuprot tome, backtracking pametno prekida nepotrebne puteve čim shvati da ne vode ka rešenju. To ga čini efikasnijim za probleme sa dodatnim uslovima i velikim brojem kombinacija, mada zahteva rekurziju u implementaciji.

U praksi, brute force se koristi kada nam je važna jednostavnost rešenja ili kada je broj slučajeva stvarno mali. Backtracking koristimo kada želimo da ubrzamo pretragu velikog prostora rešenja i možemo lako da detektujemo neuspešne puteve. Na primer, kod rešavanja sudoku slagalice, backtracking će se vratiti na prethodni korak čim detektuje da neki broj ne može da se postavi, dok bi brute force nastavio da isprobava sve druge kombinacije bez prekida.

  • Brute force: Jednostavna implementacija, isprobava sve mogućnosti, ali može biti veoma spora za veće probleme.
  • Backtracking: Rekurzivna metoda koja odbacuje nepotrebne puteve, efikasnija za kombinatorne probleme sa puno uslova, ali kod je složeniji za pisanje.

1. Put kroz lavirint

Napisati program koji ispituje da li se u pravougaonom lavirintu može stići od gornjeg levog do donjeg desnog ugla.

Ulaz:
Sa standardnog ulaza se učitavaju dimenzije lavirinta m i n razdvojene razmakom, a zatim m redova po n znakova. Polja kroz koja se može proći su označena karakterom ., a prepreke karakterom x.

Izlaz:
Ispisati da ako put postoji, odnosno ne ako put ne postoji.

Primer 1:

Ulaz
8 8
.x.....x
.x.x.x.x
.x.x.x.x
.x.x.x.x
.x.x.x.x
.x.x.x.x
.x.x.x.x
...x.x..
Izlaz
da

Primer 2:

Ulaz
8 8
.x..x..x
.x.x.x.x
.x.x.x.x
.x.x.x.x
.x...x.x
.x.x.x.x
.x.x.x.x
...x.x..
Izlaz
ne

Uputstvo za rešavanje:

  1. Pročitaj m i n, pa magistruj matricu grid dimenzija m×n.
  2. Napraviti pomoćnu matricu visited[m][n] inicijalno sa false.
  3. Implementirati rekurzivnu funkciju bool dfs(int i, int j) koja:
    • Proverava da li su (i,j) unutar granica i da je grid[i][j]=='.' i da nije već posećeno.
    • Ako je i==m-1 && j==n-1, vraća true (stigli smo do cilja).
    • Obeležava visited[i][j]=true i rekurzivno poziva samu sebe za četiri susedna polja (gore, dole, levo, desno).
    • Ako bilo koji poziv vrati true, propagira true nagore.
    • Inače vraća false.
  4. U main() pozvati dfs(0,0) i na osnovu rezultata ispisati da ili ne.

Rešenje 1: jednostavan DFS


#include <bits/stdc++.h>
using namespace std;

int m, n;
vector<string> grid;
vector<vector<bool>> visited;

// Pomoćna funkcija: proverava da li postoji put od (i,j) do (m-1,n-1)
bool dfs(int i, int j) {
    if (i < 0 || i >= m || j < 0 || j >= n)
        return false;
    if (grid[i][j] == 'x' || visited[i][j])
        return false;

    if (i == m-1 && j == n-1)
        return true;

    visited[i][j] = true;

    if (dfs(i+1, j)) return true;
    if (dfs(i-1, j)) return true;
    if (dfs(i, j+1)) return true;
    if (dfs(i, j-1)) return true;

    return false;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> m >> n;
    grid.resize(m);
    for (int i = 0; i < m; i++)
        cin >> grid[i];

    visited.assign(m, vector<bool>(n, false));

    bool postoji = dfs(0, 0);
    cout << (postoji ? "da" : "ne") << endl;
    return 0;
}

Rešenje 2: DFS sa backtracking-om

Ovaj primer vraća posećenost na false nakon ispitivanja svih puteva iz ćelije, kako bi se videlo i alternativne puteve.


#include <bits/stdc++.h>
using namespace std;

// Dimenzije lavirinta
int m, n;
// Sama mapa lavirinta
vector<string> lavirint;
// Matrica posećenosti
vector<vector<bool>> poseceno;

// Pravci kretanja: enum za četiri smera (narandzasta)
int di[4] = {-1, 1, 0, 0};
int dj[4] = {0, 0, -1, 1};

bool dfs(int i, int j) {
    if (i < 0 || i >= m || j < 0 || j >= n)
        return false;
    if (lavirint[i][j] == 'x' || poseceno[i][j])
        return false;

    if (i == m-1 && j == n-1)
        return true;

    poseceno[i][j] = true;

    for (int dir = 0; dir < 4; dir++) {
        int ni = i + di[dir];
        int nj = j + dj[dir];
        if (dfs(ni, nj))
            return true;
    }

    poseceno[i][j] = false;
    return false;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> m >> n;
    lavirint.resize(m);
    for (int i = 0; i < m; i++)
        cin >> lavirint[i];

    poseceno.assign(m, vector<bool>(n, false));

    bool postojiPut = dfs(0, 0);
    cout << (postojiPut ? "da\n" : "ne\n");
    return 0;
}

Objašnjenje


dfs(i,j) prvo proveri da li je (i,j) validna i prolazna ćelija. Ako jeste i ako je to cilj (m-1,n-1), vraća true.

Zatim obeleži tu ćeliju kao posećenu i rekurzivno pozove sebe za susedne ćelije. Ako neki od tih poziva vrati true, odmah propagira true nadole. Ako nijedan ne uspe, vrši backtracking (može da poništi oznaku posećeno) i vraća false.

Ovako implementirana DFS koristi princip backtrackinga da proba sve moguće puteve sve dok ne nađe uspešan, ili obidje ceo prostor i zaključi da puta nema.

2. Stepenasti nizovi

Napisati program koji ispisuje sve stepenaste nizove dužine n u leksikografskom poretku. Niz je stepenast ako počinje brojem 1 i svaki naredni element niza je ili jednak prethodnom ili za jedan veći od njega.

Ulaz:
Sa standardnog ulaza unosi se jedan ceo broj n (1 ≤ n ≤ 18).

Izlaz:
Ispisati sve stepenaste nizove dužine n, svaki u posebnom redu, elemente razdvojiti razmakom.

Primer:

Ulaz
3

Izlaz
1 1 1
1 1 2
1 2 2
1 2 3

Uputstvo za rešavanje:

  1. Napraviti rekurzivnu funkciju koja gradi niz dužine n postepeno.
  2. Prvi element mora biti 1. Za svaku narednu poziciju pokušati prvo da ponovimo poslednju vrednost, pa da je uvećamo za 1 (ako ne prelazi indeks+1).
  3. Kada dođemo do pozicija == n, štampati ceo niz i vratiti se.

Rešenje: Stepenasti nizovi (rekurzija)


// #include 
// #include 
// using namespace std;

// Rekurzivna funkcija:
// n        – željena dužina niza
// trenutni – vektor u kome gradimo trenutni niz
// pozicija – indeks na kome smo sada (0-based)
// poslednji – poslednja vrednost ubačena u niz
void generisiStepenasti(int n,
    vector<int>& trenutni,
    int pozicija,
    int poslednji)
{
    if (pozicija == n) {
        for (int x : trenutni) cout << x << ' ';
        cout << '\n';
        return;
    }
    // zadrži istu vrednost
    trenutni[pozicija] = poslednji;
    generisiStepenasti(n, trenutni, pozicija+1, poslednji);

    // pokušaj vrednost +1 ako ne prelazi pravilo
    if (poslednji + 1 <= pozicija + 1) {
        trenutni[pozicija] = poslednji + 1;
        generisiStepenasti(n, trenutni, pozicija+1, poslednji+1);
    }
}

int main()
{
    int n;
    cin >> n;
    vector<int> niz(n);
    // po definiciji, prvi je 1
    niz[0] = 1;
    generisiStepenasti(n, niz, 1, 1);
    return 0;
}

3. Redosledi koraka robota

Robot je iz početnog položaja napravio a koraka nadesno i b koraka naviše (gledano na mapi), ali ne znamo kojim redom. Napisati program koji ispisuje sve moguće redoslede koraka robota. Ako postoji više od 1000 različitih redosleda, ispisati samo prvih 1000.

Ulaz:
U prvom i jedinom redu se nalaze dva cela nenegativna broja, razdvojena jednim razmakom: a (i broj koraka DESNO) i b (i broj koraka GORE), oba ≤ 100.

Izlaz:
Ispisati tražene redoslede koraka, svaki u zasebnom redu. Svaki redosled prikazati kao niz reči DESNO i GORE, razdvojenih razmakom, u leksikografskom poretku (DESNO < GORE).

Primer 1:

Ulaz
3 2

Izlaz
DESNO DESNO DESNO GORE GORE
DESNO DESNO GORE DESNO GORE
DESNO DESNO GORE GORE DESNO
DESNO GORE DESNO DESNO GORE
DESNO GORE DESNO GORE DESNO
DESNO GORE GORE DESNO DESNO
GORE DESNO DESNO DESNO GORE
GORE DESNO DESNO GORE DESNO
GORE DESNO GORE DESNO DESNO
GORE GORE DESNO DESNO DESNO

Primer 2:

Ulaz
0 6

Izlaz
GORE GORE GORE GORE GORE GORE

Uputstvo za rešavanje:

  1. Koristiti rekurziju (ili backtracking) da postepeno gradimo niz od ukupno a+b koraka.
  2. U svakom pozivu znamo koliko preostalih koraka DESNO (d_rem) i GORE (g_rem) smemo još da stavimo.
  3. Prvo pokušati da dodamo DESNO (ako d_rem>0), zatim GORE (ako g_rem>0). Time je zagarantovan leksikografski redosled.
  4. Kad d_rem==0 && g_rem==0, ispisati niz i prekinuti ako smo dostigli limit od 1000 ispisa.

Rešenje: Redosledi koraka (backtracking)


// #include <iostream>
// #include <vector>
// using namespace std;

const int MAKS_IZLAZA = 1000;   // maksimalan broj redosleda za ispis
int ispisano = 0;               // brojač već ispisanih
vector<int> redosled;      // ovde gradimo niz: 0=DESNO, 1=GORE

// Rekurzivna funkcija koja gradi i ispisuje redoslede
void pretrazi(int d_rem, int g_rem) {
    if (ispisano >= MAKS_IZLAZA) return;
    if (d_rem==0 && g_rem==0) {
        // ispisujemo trenutni
        for (int i=0; i<redosled.size(); ++i) {
            if (i) cout << ' ';
            cout << (redosled[i]==0? "DESNO":"GORE");
        }
        cout << '\n';
        ++ispisano;
        return;
    }
    // prvo DESNO (jer "DESNO" < "GORE")
    if (d_rem>0) {
        redosled.push_back(0);
        pretrazi(d_rem-1, g_rem);
        redosled.pop_back();
    }
    if (ispisano >= MAKS_IZLAZA) return;
    // zatim GORE
    if (g_rem>0) {
        redosled.push_back(1);
        pretrazi(d_rem, g_rem-1);
        redosled.pop_back();
    }
}

int main() {
    int a, b;
    cin >> a >> b;
    pretrazi(a, b);
    return 0;
}

4. Binarni nizovi bez previše ponavljanja

Binarni niz je dosadan ako se u njemu pojavljuje više od k istih cifara uzastopno. Niz je interesantan ako nije dosadan. Napisati program koji ispisuje sve interesantne binarne nizove dužine n u leksikografskom poretku.

Ulaz:
Jedan red sa dva broja n i k (1 ≤ n ≤ 20, 1 ≤ k ≤ n).

Izlaz:
Sve interesantne binarne nizove dužine n, svaki u posebnom redu, bez razmaka između cifara.

Primer:

Ulaz
3 2

Izlaz
001
010
011
100
101
110

Uputstvo za rešavanje:

  1. Koristiti rekurzivnu funkciju generisi(i, poslednja, duzina, niz, n, k) koja popunjava poziciju i.
  2. Stanje:
    • poslednja – vrednost prethodnog bita (0 ili 1),
    • duzina – koliko puta uzastopno se poslednja pojavila do sada.
  3. Na svakoj poziciji pokušati prvo bit 0, pa 1 (tako da nizovi budu u leksikografskom redu).
  4. Dodavanje istog bita dozvoljeno samo ako duzina < k; promena bita uvek resetuje duzina = 1.
  5. Kad i == n, ispisati niz i vratiti se (base case).

Rešenje: Generisanje interesantnih nizova


#include <bits/stdc++.h>
using namespace std;

// Rekurzivna funkcija koja gradi niz:
//  i        – tekuca pozicija (0..n-1)
//  poslednja– vrednost prethodnog bita (0 ili 1)
//  duzina   – koliko puta uzastopno se 'poslednja' ponovila
//  niz      – vektor dužine n gde čuvamo trenutni niz
//  n, k     – duzina niza i maksimum dozvoljenih ponavljanja
void generisi(int i, int poslednja, int duzina,
              vector& niz, int n, int k) {
    if (i == n) {
        // ispisali smo ceo niz
        for (int b : niz) cout << b;
        cout << "\n";
        return;
    }
    // Pokušaj da dodamo 0
    if (poslednja != 0) {
        // menja se bit → reset dužine ponavljanja
        niz[i] = 0;
        generisi(i+1, 0, 1, niz, n, k);
    } else if (duzina < k) {
        // isti bit, ali poništavamo prevelika ponavljanja
        niz[i] = 0;
        generisi(i+1, 0, duzina+1, niz, n, k);
    }
    // Pokušaj da dodamo 1
    if (poslednja != 1) {
        niz[i] = 1;
        generisi(i+1, 1, 1, niz, n, k);
    } else if (duzina < k) {
        niz[i] = 1;
        generisi(i+1, 1, duzina+1, niz, n, k);
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, k;
    cin >> n >> k;
    vector niz(n);

    // Pošto leksikografski ide '0...' pa '1...', prvo startujemo sa 0, pa sa 1
    niz[0] = 0;
    generisi(1, 0, 1, niz, n, k);

    niz[0] = 1;
    generisi(1, 1, 1, niz, n, k);

    return 0;
}

5. Nizovi ispravno uparenih zagrada

Napisati program koji ispisuje sve nizove korektno uparenih zagrada, dužine n i dubine najviše d, u leksikografskom rastućem poretku.

Ulaz:
U prvom redu standardnog ulaza je paran broj n (1≤n≤30), a u drugom prirodan broj d (1≤d≤7). Zadata su tako da ukupno ima manje od 2000 rešenja.

Izlaz:
Ispisati sve tražene nizove zagrada u leksikografskom rastućem poretku, svaki u zasebnom redu.

Primer:

Ulaz
6
2

Izlaz
(()())
(())()
()(())
()()()

Uputstvo za rešavanje:

  1. Ustanoviti da niz mora da sadrži n/2 otvarajućih i n/2 zatvarajućih zagrada.
  2. Pratiti tri stanja pri generisanju:
    • otv – koliko otvorenih “(” smo stavili;
    • zat – koliko zatvorenih “)” smo stavili;
    • dub = otv − zat – trenutna dubina;
  3. Rekurzivno popunjavati niz na poziciji poz:
    • dodati “(” ako otv < n/2 i dub+1 ≤ d;
    • dodati “)” ako zat < otv;
  4. Prvo pokušati granu sa “(” pa zatim “)” da bi se obezbedio leksikografski poredak.
  5. Prekinuti dalje grananje čim ispisanih nizova dostigne 2000.

Rešenje: Generisanje sa ograničenjem dubine

// uključujemo sve standardne zaglavlja
#include <bits/stdc++.h>
using namespace std;

// Maksimalan broj nizova (zadato < 2000)
const int MAKS_NIZOVA = 2000;

// Ukupna dužina niza (paran broj) i dozvoljena dubina
int n, d;
// Vektor za trenutno generisani niz zagrada
vector<char> niz_zagrada;
// Brojač ispisanih nizova
int ispisano = 0;

/**
 * Rekurzivna funkcija:
 * @param poz  – trenutna pozicija u nizu (0..n-1)
 * @param otv  – broj otvorenih '(' do sada
 * @param zat  – broj zatvorenih ')' do sada
 * @param dub  – trenutna dubina = otv - zat
 */
void generisi(int poz, int otv, int zat, int dub) {
    if (ispisano >= MAKS_NIZOVA) return;       // prekid ako smo već ispisali limit
    if (poz == n) {                           // ako smo popunili ceo niz
        for (char c : niz_zagrada) cout << c;
        cout << "\n";
        ++ispisano;
        return;
    }
    // Pokušaj da dodamo '(' ako nije dostignut n/2 i dubina+1 ≤ d
    if (otv < n/2 && dub+1 <= d) {
        niz_zagrada[poz] = '(';
        generisi(poz+1, otv+1, zat, dub+1);
    }
    // Pokušaj da dodamo ')' ako ima više otvorenih nego zatvorenih
    if (zat < otv) {
        niz_zagrada[poz] = ')';
        generisi(poz+1, otv, zat+1, dub-1);
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    // Učitavamo n i d
    cin >> n >> d;
    niz_zagrada.resize(n);

    // Pokrećemo rekurziju od početka niza
    generisi(0, 0, 0, 0);
    return 0;
}
/*
Objašnjenje:
- n mora biti paran (po pola '(' i ')').
- d ograničava maksimalnu razliku (otvoreni - zatvoreni) u bilo kom trenutku.
- Grana sa '(' se bira prva da bi leksikografski nizovi sa '(' redom bili pre onih sa ')'.
- Brojač ispisano sprečava prelazak 2000 rešenja.
*/

6. Maksimalni bezbedni put

Dato je n × m polje u kome svaka ćelija ili sadrži minu (0) ili nenegativan broj. Potrebno je iz bilo kog polja prve kolone stići do bilo kog polja poslednje kolone bezbednim putem: niti na polju niti na nekom njegovom susedu (gore, dole, levo, desno) ne sme biti mina. Kretanje je dozvoljeno gore, dole, levo i desno, a svako polje sme se obići najviše jednom. Izračunati maksimalnu sumu brojeva kroz neku takvu bezbednu stazu ili ispisati -1 ako puta nema.

Ulaz:
Prvi red: dva broja m, n (1<m,n≤20). Sledeće n redova po m brojeva matrice.

Izlaz:
Jedan ceo broj – maksimalna suma ili -1 ako bezbedan put ne postoji.

Primer:

Ulaz
4 4
5 1 2 0
1 2 3 4
2 4 1 1
0 1 1 1

Izlaz
17

Uputstvo za rešavanje:

  1. Obeležavanje nebezbednih polja: Polja sa 0 i njihovi susedi se obeleže u matrici nebezbedno.
  2. DFS pretraga:
    • Od svake sigurne ćelije prve kolone pokreće se rekurzija.
    • Prati se poseceno da se ne bi ulazilo u ciklus.
    • U svakoj rekurziji, kad se stigne do poslednje kolone, ažurira se globalni maksimum sume.
  3. Backtracking: nakon istraživanja svakog suseda poništava se poseceno kako bi se dozvolile druge staze.
  4. Rezultat: Ako je najvecaSuma ostala -1, nema puta; inače se ta vrednost ispisuje.

// C++ implementation of the maximal safe path problem
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int m, n;
vector<vector<int>> A;
vector<vector<bool>> blocked, seen;
int best = -1;

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

bool valid(int x, int y) {
  return x >= 0 && x < n && y >= 0 && y < m;
}

void markBlocked() {
  blocked.assign(n, vector<bool>(m, false));
  for(int i=0; i<n; ++i) {
    for(int j=0; j<m; ++j) {
      if(A[i][j] == 0) {
        blocked[i][j] = true;
        for(int d=0; d<4; ++d) {
          int ni = i + dx[d], nj = j + dy[d];
          if(valid(ni,nj)) blocked[ni][nj] = true;
        }
      }
    }
  }
}

void dfs(int x, int y, int sum) {
  if(!valid(x,y) || blocked[x][y] || seen[x][y]) return;
  if(y == m - 1) {
    best = max(best, sum + A[x][y]);
    return;
  }
  seen[x][y] = true;
  for(int d=0; d<4; ++d) {
    int nx = x + dx[d], ny = y + dy[d];
    dfs(nx, ny, sum + A[x][y]);
  }
  seen[x][y] = false;
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  cin >> m >> n;
  A.assign(n, vector<int>(m));
  for(int i=0; i<n; ++i)
    for(int j=0; j<m; ++j)
      cin >> A[i][j];

  markBlocked();
  seen.assign(n, vector<bool>(m, false));
  for(int i=0; i<n; ++i) {
    if(!blocked[i][0]) dfs(i, 0, 0);
  }
  cout << (best==-1?-1:best) << "\n";
  return 0;
}

7. Obojeni lavirint

Ispred tebe je m × n matrica u kojoj je svako polje obojeno jednom od četiri boje: 1 (crveno), 2 (plavo), 3 (žuto) ili 4 (zeleno). Polje mora da počneš sa crvenim (1), a zatim se krećeš u niz cikličnog sleđenja boja: 1→2→3→4→1→2… samo u četiri smera (gore, dole, levo, desno), i nijedno polje ne smeš posetiti više puta. Proveri da li postoji put sa bilo kog polja u donjem redu do bilo kog polja u gornjem redu koji zadovoljava ova pravila.

Ulaz:
Prvi red: dva broja m (broj kolona) i n (broj redova), (1 ≤ m,n ≤ 20).
Sledećih n redova: po m cifara bez razmaka koje predstavljaju boje polja.

Izlaz:
Ispisati da ako takav put postoji, ili ne ako ne postoji.

Primer:


 Ulaz 
5 6 
143222 
414344 
323244 
124123 
343211

Izlaz
da

Uputstvo za rešavanje:

  1. DFS/BFS pretraga:
    • Počni od svakog polja u donjem redu koje je obojeno 1 (crveno).
    • Drži matricu poseceno da ne bi ulazio u ciklus.
    • Na svakom koraku proveri boju narednog polja: ako si trenutno na boji c, dozvoljen prelaz je na boju (c % 4) + 1.
    • Ako DFS stigne do bilo kog polja u gornjem redu (y == n–1), odgovor je da.
  2. Backtracking: nakon svakog uspona poništiti poseceno da bi se ispitali svi putevi.
  3. Rezultat: ako nijedna pretraga ne uspe, ispisati ne.

// C++ rešenje za obojeni lavirint
#include <iostream>
#include <vector>
using namespace std;

int m, n; // dimenzije matrice
vector<vector<int>> boja;    // matrica boja
vector<vector<bool>> poseceno; // posećena polja

int dx[4] = { -1, 1, 0, 0 }, dy[4] = { 0, 0, -1, 1 }; // smerovi kretanja

bool validno(int x, int y) {
  return x >= 0 && x < n && y >= 0 && y < m;
}

bool dfs(int x, int y) {
  if(!validno(x,y) || poseceno[x][y])
    return false;
  poseceno[x][y] = true;

  int trenutna = boja[x][y];
  int sledeca = (trenutna % 4) + 1;

  if(x == 0) 
    return true; // stigli do gornjeg reda

  for(int d = 0; d < 4; ++d) {
    int nx = x + dx[d], ny = y + dy[d];
    if(validno(nx,ny)
       && boja[nx][ny] == sledeca
       && !poseceno[nx][ny]) {
      if(dfs(nx,ny))
        return true;
    }
  }

  poseceno[x][y] = false; // backtracking
  return false;
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  cin >> m >> n;
  boja.assign(n, vector<int>(m));
  for(int i = 0; i < n; ++i) {
    string red; cin >> red;
    for(int j = 0; j < m; ++j)
      boja[i][j] = red[j] - '0';
  }

  poseceno.assign(n, vector<bool>(m, false));

  bool postoji = false;
  for(int j = 0; j < m; ++j) {
    if(boja[n-1][j] == 1) {
      if(dfs(n-1, j)) {
        postoji = true;
        break;
      }
    }
  }

  cout << (postoji ? "da\n" : "ne\n");
  return 0;
}

8. Padajuća loptica

Loptica se ispušta sa visine i pada kroz prostor ispunjen preprekama. Kada ispod nje nema prepreka, ona pada direktno naniže. Kada je prepreka ispod nje, ona se zaustavlja i tada je možemo gurnuti bilo levo, bilo desno do ivice prepreke, nakon čega ona nastavlja da pada. Napiši program koji određuje da li loptica može da dođe do dna.

Ulaz:
Sa standardnog ulaza se učitava matrica karaktera do kraja ulaza (svi redovi standardnog ulaza su iste dužine i predstavljaju redove matrice). Ni dužina ni širina matrice nisu veći od 16. Prepreke su označene karakterom x, praznine karakterom ., dok je početni položaj loptice određen karakterom O i nalazi se u najvišoj vrsti.

Izlaz:
Na standardni izlaz ispisati da ako loptica može da padne do dna ili ne ako ne može.

Primer 1:

Ulaz
O.......x...x
xxx.....xx..x
xxx....xxx.xx
xxxx........x
xxxx..xx....x
xxxxxxxx.xxxx

Izlaz
ne

Primer 2:

Ulaz
.O......x...x
xxx.....xx..x
.......xxx.xx
.xxx........x
.xxxxx.x....x
.xxxxxxx.xxxx

Izlaz
da

Uputstvo za rešavanje:

  1. Učitavanje matrice:
    • Čitaju se svi redovi iz standardnog ulaza u vektor stringova grid.
    • Odrediti broj redova R i broj kolona C (dužina prvog reda).
  2. Pronalazak početne pozicije:
    • U prvom redu pronaći kolonu startC gde se nalazi karakter O.
    • Zameniti to polje sa '.' kako bi padanje lakše obrađivali.
  3. Implementacija DFS pretrage (dfs(r,c)):
    • Koristimo dvodimenzionalni niz visited[R][C] da ne bismo ponovo istraživali isto stanje.
    • Faza gravitiranja:
      • Postaviti rr = r i zatim pomerati naniže sve dok je ispod '.' (prazno).
      • Ako rr + 1 == R (stigli smo do poslednjeg reda), vratiti true jer je put do dna pronađen.
    • Ako je grid[rr+1][c] == 'x', onda je loptica zaustavljena na (rr, c).
    • Detekcija leve i desne ivice bloka ispod:
      • Postaviti left = c i pomerati ulevo sve dok grid[rr+1][left-1] == 'x'.
      • Postaviti right = c i pomerati udesno sve dok grid[rr+1][right+1] == 'x'.
    • Pokušati pomeranje loptice levo i desno:
      • Ako je left-1 ≥ 0 i grid[rr][left-1] == '.', rekurzivno pozvati dfs(rr, left-1).
      • Ako je right+1 < C i grid[rr][right+1] == '.', rekurzivno pozvati dfs(rr, right+1).
      • Ako bilo koja od ovih rekurzija vrati true, vratiti true.
    • Ako nijedno pomeranje ne uspe, vratiti false.
  4. Glavni tok programa:
    • Inicializovati visited na false u svim ćelijama.
    • Pozvati dfs(0, startC) i dobiti rezultat može.
    • Ispisati "da" ako je može == true, inače "ne".

#include <bits/stdc++.h>
using namespace std;

/*
  Padajuća loptica

  Matrica dimenzija ≤16×16, sa:
   - 'O' početna pozicija loptice u najvišem redu
   - 'x' prepreke
   - '.' praznine

  Pravila:
   1. Loptica pada naniže dok ne naiđe na prepreku ili dno matrice.
   2. Kada se zaustavi iznad prepreke, može se gurnuti levo ili desno do ivice tog bloka prepreka,
      zatim nastavlja da pada sa te nove kolone.
   3. Cilj: da li loptica može da dosegne najniži red?
*/

int R, C;
vector grid;
bool visited[16][16];  // markiranje već posećenih stanja (red, kolona)

/*
  Rekurzivna funkcija koja simulira lopticu
  počevši od položaja (r,c).
  Vraća true ako postoji put do dna.
*/
bool dfs(int r, int c) {
    // Ako smo već obišli ovu ćeliju, nema potrebe ponovo
    if (visited[r][c]) return false;
    visited[r][c] = true;

    // Pustimo lopticu da pada
    int rr = r;
    while (rr + 1 < R && grid[rr + 1][c] == '.') {
        rr++;
    }
    // Ako je stigla do dna
    if (rr + 1 == R) return true;

    // Sada je ispod prepreka na poziciji (rr+1,c)
    // rr je red iznad bloka x-ova
    // Nađimo levu i desnu ivicu tog bloka prepreka
    int left = c, right = c;
    // širimo ulevo
    while (left - 1 >= 0 && grid[rr + 1][left - 1] == 'x') {
        left--;
    }
    // širimo udesno
    while (right + 1 < C && grid[rr + 1][right + 1] == 'x') {
        right++;
    }

    // Kandidati za novi pad su:
    // (rr, left-1) i (rr, right+1), ako su unutar granica i prazni
    bool ok = false;
    if (left - 1 >= 0 && grid[rr][left - 1] == '.') {
        ok |= dfs(rr, left - 1);
    }
    if (right + 1 < C && grid[rr][right + 1] == '.') {
        ok |= dfs(rr, right + 1);
    }
    return ok;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    // Učitavamo celu matricu dok traje ulaz
    string line;
    grid.clear();
    while (getline(cin, line)) {
        if (!line.empty()) {
            grid.push_back(line);
        }
    }
    R = grid.size();
    if (R == 0) return 0;
    C = grid[0].size();

    // Pronađemo početnu kolonu 'O' u prvom redu
    int startC = -1;
    for (int j = 0; j < C; j++) {
        if (grid[0][j] == 'O') {
            startC = j;
            break;
        }
    }

    // Obeležimo početni položaj kao prazno da se lakše radi
    grid[0][startC] = '.';

    // Čistimo visited
    memset(visited, 0, sizeof(visited));

    // Pokrećemo DFS
    bool može = dfs(0, startC);

    cout << (može ? "da" : "ne") << "\n";
    return 0;
}
/*
Objašnjenje algoritma:

1. Učitavanje i priprema:
   - Čitaju se svi redovi u vektor grid.
   - Određuju se dimenzije R (broj redova) i C (broj kolona).
   - Pronalazi se kolona startC gde stoji 'O' u najvišem redu.
   - To polje se tretira kao prazno '.' jer loptica tu treba da počne pad.

2. DFS pretraga (dfs(r,c)):
   - Ako je stanje (r,c) već posećeno, vraća se false.
   - Obeležava se visited[r][c] = true.
   - Loptica pada naniže promenom rr dok je ispod prazno '.'. 
     Ako rr + 1 == R, stigli smo do dna ⇒ vraća se true.
   - Inače se ispod bloka nalazi 'x' na (rr+1, c). 
     Onda je loptica zaustavljena na (rr, c).
   - Pronalaze se leve i desne ivice kontinualnog bloka 'x' ispod:
     left se smanjuje dok grid[rr+1][left-1] == 'x'.
     right se povećava dok grid[rr+1][right+1] == 'x'.
   - Pokušava se rekurzija sa pozicija:
     (rr, left-1) i (rr, right+1), ako su unutar granica i prazne '.'.
     Ako bilo koji poziv vrati true, vraća se true.
   - Ako nijedan ne uspe, vraća se false.

3. Glavni tok:
   - Inicijalizuje se niz visited na false.
   - Poziva se dfs(0, startC). Ako je rezultat true, ispisuje se "da", inače "ne".

Complexity:
- Veličina matrice je max 16×16, pa DFS istražuje ograničen broj stanja (svako stanje se obiđe najviše jednom).
- Algoritam je dovoljan za brz ishod u svakoj instanci dimenzija ≤ 16×16.
*/

9. Raspoređivanje n dama na šahovskoj tabli


Napiši program koji određuje sve položaje n dama na šahovskoj tabli dimenzije n × n tako da se nijedne dve dame međusobno ne napadaju. Svaka vrsta mora sadržati tačno jednu damu, a nijedne dve dame ne smeju biti u istoj koloni ili na istoj dijagonali. Raspored je predstavljen nizom od n različitih brojeva od 1 do n, gde svaka vrednost označava kolonu u kojoj dama stoji u odgovarajućoj vrsti.

Ulaz:
Jedan prirodan broj n (4 ≤ n ≤ 11).

Izlaz:
Sve moguće rasporede dama, po jedan raspored po redu. Svaki raspored se ispisuje kao n brojeva odvojenih razmakom, gde broj na poziciji i označava kolonu dame u vrsti i. Redosled rešenja može biti proizvoljan.

Primer:

Ulaz
4
Izlaz
3 1 4 2
2 4 1 3

Uputstvo za rešavanje:

  1. Predstavljanje rasporeda: Raspored se čuva u nizu pozicija[1..n], gde pozicija[i] označava kolonu u kojoj stoji dama u vrsti i.
  2. Provera napada: Kada postavljamo damu u vrstu i i kolonu k, proverava se da li bilo koja ranije postavljena dama u vrsti j < i nema:
    • pozicija[j] == k — iste kolone;
    • |pozicija[j] - k| == |j - i| — iste dijagonale (glavna ili sporedna).
  3. Backtracking:
    • Započinjemo od vrste 1 i pokušavamo da damu postavimo u svaku kolonu od 1 do n.
    • Ako je postavka za vrstu i važeća, rekurzivno prelazimo na vrstu i+1.
    • Ako dođemo do vrste n+1, znači da smo uspešno postavili sve dame i ispisujemo trenutno rešenje.
    • Nakon što pokušamo sve kolone za vrstu i, vraćamo se (backtrack) u prethodnu vrstu i menjamo kolonu dame.
  4. Efikasnost: Ovaj backtracking algoritam izbegava beskonačne provere tako što odmah odbacuje nevažeće postavke (uzrast konflikt), čime se značajno smanjuje broj provera u odnosu na „grubu silu“. 

#include 
#include 
using namespace std;

// Maksimalna vrednost n prema uslovu (n ≤ 11)
int n;

// Niz u kome će biti smeštena kolona dame u svakoj vrsti (1..n)
vector pozicija;

// Logički nizovi koji beleže da li je kolona ili dijagonala zauzeta
vector koloneZauzete;
vector dijagonalnaZauzeta1; // i - j + (n - 1) indeks
vector dijagonalnaZauzeta2; // i + j indeks

void ispisiResenje() {
    for (int i = 1; i <= n; ++i) {
        cout << pozicija[i];
        if (i < n) cout << " ";
    }
    cout << "\n";
}

// Provera da li je bezbedno postaviti damu u vrstu i i kolonu k
bool mozePostaviti(int i, int k) {
    int idx1 = i - k + (n - 1); // glavna dijagonala
    int idx2 = i + k;           // sporedna dijagonala
    return !koloneZauzete[k] && !dijagonalnaZauzeta1[idx1] && !dijagonalnaZauzeta2[idx2];
}

// Rekurzivna funkcija za postavljanje dama
void postaviDame(int i) {
    if (i > n) {
        ispisiResenje(); // nađeno rešenje
        return;
    }
    for (int k = 1; k <= n; ++k) {
        int idx1 = i - k + (n - 1);
        int idx2 = i + k;
        if (mozePostaviti(i, k)) {
            // Postavi damu
            pozicija[i] = k;
            koloneZauzete[k] = true;
            dijagonalnaZauzeta1[idx1] = true;
            dijagonalnaZauzeta2[idx2] = true;

            // Nastavi rekurzivno
            postaviDame(i + 1);

            // Ukloni oznake (backtrack)
            koloneZauzete[k] = false;
            dijagonalnaZauzeta1[idx1] = false;
            dijagonalnaZauzeta2[idx2] = false;
            pozicija[i] = 0;
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n;

    // Inicijalizacija nizova
    pozicija.assign(n + 1, 0);
    koloneZauzete.assign(n + 1, false);
    dijagonalnaZauzeta1.assign(2 * n, false);
    dijagonalnaZauzeta2.assign(2 * n + 1, false);

    postaviDame(1);
    return 0;
}

Za detaljno objašnjenje 5 varijanti rešenja, uključujući kodove i komentare, pogledajte analizu svih 5 rešenja N kraljica .

10. Rešavač Sudokua


Napiši program koji rešava zadati Sudoku pomoću backtracking algoritma. Sudoku je matrica dimenzije 9×9 koja se sastoji od 9 redova, 9 kolona i 9 unutrašnjih kvadrata veličine 3×3. Cilj je popuniti prazna polja (označena nulama) brojevima od 1 do 9 tako da se u svakom redu, svakoj koloni i svakom kvadratu od 3×3 brojevi ne ponavljaju.

Ulaz:
9 redova po 9 brojeva, gde nula označava prazno polje.

Izlaz:
Popunjena Sudoku tabla ako rešenje postoji, odnosno poruka Nema rešenja ako nije moguće popuniti tablu.

Primer:

Ulaz:
0 0 3 0 2 0 6 0 0
9 0 0 3 0 5 0 0 1
0 0 1 8 0 6 4 0 0
0 0 8 1 0 2 9 0 0
7 0 0 0 0 0 0 0 8
0 0 6 7 0 8 2 0 0
0 0 2 6 0 9 5 0 0
8 0 0 2 0 3 0 0 9
0 0 5 0 1 0 3 0 0

Izlaz:
4 8 3 9 2 1 6 5 7
9 6 7 3 4 5 8 2 1
2 5 1 8 7 6 4 9 3
5 4 8 1 3 2 9 7 6
7 2 9 5 6 4 1 3 8
1 3 6 7 9 8 2 4 5
3 7 2 6 8 9 5 1 4
8 1 4 2 5 3 7 6 9
6 9 5 4 1 7 3 8 2

Uputstvo za rešavanje:

  1. Sudoku se rešava pomoću backtracking pristupa, gde program pokušava da popuni prazna polja jedno po jedno.
  2. Za svako prazno polje proverava da li je sigurno postaviti broj od 1 do 9 (provera se vrši po redu, koloni i unutrašnjem kvadratu 3×3).
  3. Ako je broj validan, program ga postavlja i rekurzivno prelazi na sledeće prazno polje.
  4. Ako dođe do zastoja (nema mogućeg broja), program se vraća korak unazad (tzv. backtracking) i menja prethodni izbor.
  5. Kada su sva polja popunjena, Sudoku je rešen.

// C++ rešenje problema rešavanja Sudokua pomoću backtracking algoritma
#include <iostream>
#include <vector>
using namespace std;

// Funkcija koja proverava da li se broj može sigurno postaviti na poziciju (r, c)
bool sigurno(vector<vector<int>> &tabela, int r, int c, int vrednost) {
    // Provera reda i kolone
    for(int i = 0; i < 9; i++) {
        if(tabela[r][i] == vrednost || tabela[i][c] == vrednost)
            return false;
    }
    // Provera kvadrata 3×3
    int pocReda = (r / 3) * 3;
    int pocCol = (c / 3) * 3;
    for(int i = pocReda; i < pocReda + 3; i++) {
        for(int j = pocCol; j < pocCol + 3; j++) {
            if(tabela[i][j] == vrednost)
                return false;
        }
    }
    return true;
}

// Glavna rekurzivna funkcija koja pokušava da reši Sudoku
bool sudoku(vector<vector<int>> &tabela) {
    for(int r = 0; r < 9; r++) {
        for(int c = 0; c < 9; c++) {
            if(tabela[r][c] == 0) {
                for(int vrednost = 1; vrednost <= 9; vrednost++) {
                    if(sigurno(tabela, r, c, vrednost)) {
                        tabela[r][c] = vrednost;
                        if(sudoku(tabela))
                            return true;
                        tabela[r][c] = 0; // vraćanje unazad
                    }
                }
                return false; // nema validnog broja
            }
        }
    }
    return true; // tabla popunjena
}

int main() {
    vector<vector<int>> tabla(9, vector<int>(9));
    for(int i = 0; i < 9; i++)
        for(int j = 0; j < 9; j++)
            cin >> tabla[i][j];

    if(sudoku(tabla)) {
        for(int i = 0; i < 9; i++) {
            for(int j = 0; j < 9; j++)
                cout << tabla[i][j] << (j == 8 ? '\n' : ' ');
        }
    } else {
        cout << "Nema rešenja" << endl;
    }
    return 0;
}
Algoritmi
Matrice
Java
Linkovi
​Politika Privatnosti
Kontakt

© 2025 by Slobodan svetprogramiranja.com

Sva prava zadržana
SVET PROGRAMIRANJA