hack

Hack

== include(page="template/taskheader" task_id="hack") ==

La ultimul concurs de pe 'Codeforces':http://codeforces.com/, 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.
 

== code(c) |

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

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

const int STEPS = 1;

const int INFINIT = 1000000;

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

void message(int points, string mess) {
    cout << points << "\n";
    cerr << mess << "\n";
    exit(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, n * m));

    vector<VI> d(n, vector<int> (m, INFINIT));

    d[start.first][start.second] = 0;
    Q.push(start);

    return COUNTER;
}

==

int main() {
 
    ifstream cin("hack.out");
 
    int n, m, startX, startY;
 
    if(!(cin >> n >> m >> startX >> startY))
        message(0, "Fisier de iesire incomplet");
 
    if(startX < 1 || startX > n || startY < 1 || startY > m)
        message(0, "Incorect.\n");
 
    vector<string> A(n);

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

    for(int i = 0; i < n; ++i) {
        if(!(cin >> A[i]))
            message(0, "Fisier de iesire incomplet.\n");
        if((int) A[i].size() < m)
            message(0, "Fisier de iesire incomplet.\n");
    }
 
    int ans = getDistance(A, {startX, startY});

==code(c) |

    if(ans >= STEPS)
        message(100, to_string(ans) + " pasi.");
 
    message(0, "Prea putini pasi :(.");
}

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

h2. Date de intrare

Fişierul de intrare $hack.in$ ...

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

h2. Date de ieşire

În fişierul de ieşire $hack.out$ ...

Î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$.

h2. Restricţii

* $... ≤ ... ≤ ...$

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

h2. Exemplu
table(example). |_. hack.in |_. hack.out |

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

| Erau odată doi cerbi. Unul era atât de slab,
 încât i se vedeau coastele tot timpul. Celălalt
 avea coarnele neobişnuit de mari.
 Se numeau Costel şi Cornel.
|5 5 3 3
00000
01110
01010
01110
00000

|
h3. Explicaţie

...
 

== include(page="template/taskfooter" task_id="hack") ==