Fişierul intrare/ieşire:	hack.in, hack.out	Sursă	FMI No Stress 6
Autor	Mihai Calancea	Adăugată de	FMI No Stress •fmins123
Timp execuţie pe test	0.5 sec	Limită de memorie	20480 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

Hack

La ultimul concurs de pe Codeforces, ai avut de rezolvat următoarea problemă: Dându-se o matrice de dimensiuni N x M cu celule de valoare 0 sau 1 şi o celulă de start, determinaţi costul minim de a ajunge din celula de start în toate celelalte celule. O mişcare constă în schimbarea celulei curente cu una adiacentă pe cele 4 direcţii cardinale, fără a părăsi la niciun punct matricea. Costul mişcării este 0 dacă şi numai dacă cele două celule între care s-a călătorit au aceeaşi valoare. Altfel, costul este 1.

Bineînţeles, tu ai rezolvat corect această problemă, doar eşti omniscient. Acum doreşti să examinezi codul altor participanţi şi eventual să găseşti teste pe care soluţia lor nu funcţionează sau funcţionează prea încet. În sursa unui anumit concurent ai găsit următoarea funcţie care calculează distanţele folosind un algoritm similar cu parcurgerea în lăţime / BFS, folosindu-se de o coadă. Eşti sigur că acest cod este totuşi ineficient. Trebuie să găseşti un test de dimensiuni N x M, cu N şi M maxim de valoare maxim 50, astfel încât valoarea variabilei COUNTER să fie cât mai mare după execuţia funcţiei.

#define PII pair<int, int>
#define VI vector<int>

const int INFINIT = 1000000;
const int dx[5] = {0, 0, 1, -1};
const int dy[5] = {1, -1, 0, 0};

int getDistance(vector<string> &A, PII start) {
    int n = A.size(), m = A[0].size();
    int COUNTER = 0;

    start.first--, start.second--; // reindexam de la 0.

    queue<PII> Q;
    vector<VI> d(n, vector<int> (m, INFINIT)); 
    d[start.first][start.second] = 0;
    Q.push(start);
    
    while(!Q.empty()) {
        PII node = Q.front();
        Q.pop();
        
        COUNTER++;

        for(int dir = 0; dir < 4; ++dir) {
            int newX = node.first + dx[dir];
            int newY = node.second + dy[dir];
            if(newX < 0 || newX >= n || newY < 0 || newY >= m)
                continue;
            int cost = 0;
            if(A[node.first][node.second] != A[newX][newY]) 
                cost = 1;
            
            if(d[node.first][node.second] + cost < d[newX][newY]) {
                d[newX][newY] = d[node.first][node.second] + cost;
                Q.push({newX, newY});
            }
        }
    }

    return COUNTER;
}

Punctajul vostru va fi calculat astfel, formula fiind valabilă doar dacă COUNTER este cel puţin 2500. Altfel, punctajul este 0.

int POINTS = floor((min(COUNTER, 18000) - 2500.0) / (18000 - 2500) * 100);

Pe scurt, pentru 100 de puncte trebuie ca variabila COUNTER să fie mai mare sau egală cu valoarea 18.000.

Date de intrare

Fişierul de intrare hack.in nu va conţine nimic.

Date de ieşire

În fişierul de ieşire hack.out se vor afla 4 numere pe prima linie: N, M, startX, startY, reprezentând dimensiunile matricei şi coordonatele celulei de start. startX startY vor fi indexate de la 1.

Restricţii

• 1 ≤ N, M ≤ 50
• Enunţul este fictiv, nu căutaţi ultimul concurs de pe Codeforces.

Exemplu

Explicaţie

Cum se trimit solutii?