Zadaci – takmičenje

Stefan pokušava da otvori sef pomoću metalnog prstena na kome su ucrtani znakovi. Prsten se može rotirati u smjeru kazaljke na satu ili u suprotnom smjeru kako bi se određeni znak poravnao sa pozicijom „12:00“. Кod za otključavanje sefa dat je u nizu s2, dok je prsten predstavljen nizom s1. Na prstenu se svaki znak pojavljuje tačno jednom, tj. svi znakovi u s1 su jedinstveni. Stefan može: Rotirati prsten ulijevo ili udesno kako bi ciljni znak došao na poziciju „12:00“. Pritisnuti dugme kako bi zapisao taj znak. Vaš zadatak je da odredite minimalan broj koraka koji su potrebni da se unese čitav niz s2. Broj koraka računa se kao broj rotacija + broj pritisaka dugmeta.

#include <iostream>
#include <string>
#include <unordered_map>
#include <cmath>

using namespace std;

int minimalniKoraci(string s1, string s2) {
    int n = s1.length();
    
    // mapa znak -> pozicija u prstenu
    unordered_map<char, int> pozicija;
    for (int i = 0; i < n; i++) {
        pozicija[s1[i]] = i;
    }

    int trenutna = 0;
    int koraci = 0;

    for (char c : s2) {
        int cilj = pozicija[c];

        int diff = abs(cilj - trenutna);
        int rotacija = min(diff, n - diff);

        koraci += rotacija + 1; // +1 za pritisak dugmeta
        trenutna = cilj;
    }

    return koraci;
}

int main() {
    string s1, s2;

    cin >> s1;
    cin >> s2;

    cout << minimalniKoraci(s1, s2) << endl;

    return 0;
}

Data je matrica koja predstavlja simulaciju svima dobro poznate igre iks-oks. Potrebno je pronaći najmanji
broj koraka kako bi se igra završila pobjedom ili nerješenim rezultatom. Igrač iks prvi počinje igru i zatim
igraju naizmjenično.
Ulaz:
U prvoj liniji se nalaze tri karaktera odvojena razmakom. Tri moguća karaktera su ‘X’, ‘O’ i ‘_’ gdje
zadnji karakter predstavlja prazno polje. U drugoj i trećoj liniji se takođe nalaze po tri karaktera
odvojena razmakom.
Izlaz:
Cijeli broj koji predstavlja minimalan broj koraka kako bi se igra završila pobjedom ili
nerješenim rezultatom.

#include <iostream>
#include <algorithm>

using namespace std;

bool pobjeda(char a[3][3], char p) {
    for(int i = 0; i < 3; i++) {
        if(a[i][0] == p && a[i][1] == p && a[i][2] == p) return true;
        if(a[0][i] == p && a[1][i] == p && a[2][i] == p) return true;
    }

    if(a[0][0] == p && a[1][1] == p && a[2][2] == p) return true;
    if(a[0][2] == p && a[1][1] == p && a[2][0] == p) return true;

    return false;
}

bool puna(char a[3][3]) {
    for(int i = 0; i < 3; i++)
        for(int j = 0; j < 3; j++)
            if(a[i][j] == '_')
                return false;
    return true;
}

int dfs(char a[3][3], char igrac) {

    if(pobjeda(a,'X') || pobjeda(a,'O') || puna(a))
        return 0;

    int najbolji = 100;

    for(int i = 0; i < 3; i++) {
        for(int j = 0; j < 3; j++) {

            if(a[i][j] == '_') {

                a[i][j] = igrac;

                char sljedeci = (igrac == 'X') ? 'O' : 'X';

                najbolji = min(najbolji, 1 + dfs(a, sljedeci));

                a[i][j] = '_';
            }
        }
    }

    return najbolji;
}

int main() {

    char a[3][3];
    int x = 0, o = 0;

    for(int i = 0; i < 3; i++) {
        for(int j = 0; j < 3; j++) {
            cin >> a[i][j];

            if(a[i][j] == 'X') x++;
            if(a[i][j] == 'O') o++;
        }
    }

    char igrac = (x == o) ? 'X' : 'O';

    cout << dfs(a, igrac) << endl;

    return 0;
}