BEKTREKING I GRUBA SILA- PRIMERI

Rešenje 1: jednostavan DFS

#include<bits/stdc++.h>usingnamespacestd;

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)booldfs(int i, int j) {
    if (i < 0 || i >= m || j < 0 || j >= n)
        returnfalse;
    if (grid[i][j] =='x'||visited[i][j])
        returnfalse;

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

    visited[i][j] =true;

    if (dfs(i+1, j)) returntrue;
    if (dfs(i-1, j)) returntrue;
    if (dfs(i, j+1)) returntrue;
    if (dfs(i, j-1)) returntrue;

    returnfalse;
}

intmain() {
    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;
    return0;
}
  

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>usingnamespacestd;

// 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};

booldfs(int i, int j) {
    if (i <0|| i >= m || j <0|| j >= n)
        returnfalse;
    if (lavirint[i][j] =='x'|| poseceno[i][j])
        returnfalse;

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

    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))
            returntrue;
    }

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

intmain() {
    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");
    return0;
}
  

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;
}
      

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;
}
      

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;
}
      

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.
*/
      

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

intm, n;
vector<vector<int>> A;
vector<vector<bool>> blocked, seen;
intbest = -1;

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

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

voidmarkBlocked() {
  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;
        }
      }
    }
  }
}

voiddfs(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;
}

intmain() {
  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";
  return0;
}
      

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

intm, n; // dimenzije matricevector<vector<int>> boja;    // matrica bojavector<vector<bool>> poseceno; // posećena poljaintdx[4] = { -1, 1, 0, 0 }, dy[4] = { 0, 0, -1, 1 }; // smerovi kretanjaboolvalidno(int x, int y) {
  return x >= 0 && x < n && y >= 0 && y < m;
}

booldfs(int x, int y) {
  if(!validno(x,y) || poseceno[x][y])
    returnfalse;
  poseceno[x][y] = true;

  inttrenutna = boja[x][y];
  intsledeca = (trenutna % 4) + 1;

  if(x == 0) 
    returntrue; // stigli do gornjeg redafor(int d = 0; d < 4; ++d) {
    intnx = x + dx[d], ny = y + dy[d];
    if(validno(nx,ny)
       && boja[nx][ny] == sledeca
       && !poseceno[nx][ny]) {
      if(dfs(nx,ny))
        returntrue;
    }
  }

  poseceno[x][y] = false; // backtrackingreturnfalse;
}

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

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

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

  boolpostoji = 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;
}

#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.
*/
      

#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;
}
      

// 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)boolsigurno(vector<vector<int>> &tabela, int r, int c, int vrednost) {
    // Provera reda i kolonefor(int i = 0; i < 9; i++) {
        if(tabela[r][i] == vrednost || tabela[i][c] == vrednost)
            return false;
    }
    // Provera kvadrata 3×3int 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 Sudokuboolsudoku(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
}

intmain() {
    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;
}