Cod sursa(job #2415968)

Utilizator catalintermureTermure Catalin catalintermure Data 26 aprilie 2019 17:46:52
Problema Castel Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.33 kb
#include <fstream>
#include <iostream>

using namespace std;

ifstream inf("castel.in");
ofstream outf("castel.out");

constexpr int NMAX = 152;

int v[NMAX][NMAX];
pair<int, int> q[NMAX * NMAX];
bool hasKey[NMAX * NMAX];
bool viz[NMAX][NMAX];
int n, m;
const int di[4] = {-1, 1, 0, 0};
const int dj[4] = {0, 0, -1, 1};

inline pair<int, int> getCoord(int x) {
    return {(x - 1) / m + 1, (x - 1) % m + 1};
}

int main() {
    int k;
    inf >> n >> m >> k;
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= m; j++) {
            inf >> v[i][j];
        }
    }
    bool ok = true;
    int dr = 0, i, j, ii, jj;
    q[dr++] = getCoord(k);
    viz[q[0].first][q[0].second] = true;
    hasKey[k] = true;
    do {
        ok = true;

        for(int st = 0; st < dr; st++) {
            i = q[st].first;
            j = q[st].second;
            for(int k = 0; k < 4; k++) {
                ii = i + di[k];
                jj = j + dj[k];
                if(hasKey[v[ii][jj]] && !viz[ii][jj]) {
                    ok = false;
                    hasKey[ii * m - m + jj] = true;
                    q[dr++] = {ii, jj};
                    viz[ii][jj] = true;
                }
            }
        }

    } while(!ok);
    outf << dr << '\n';
    inf.close();
    outf.close();
    return 0;
}