Cod sursa(job #2395237)

Utilizator catalintermureTermure Catalin catalintermure Data 2 aprilie 2019 12:43:22
Problema Castel Scor 80
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.92 kb
#include <fstream>
#include <vector>
#include <iostream>

using namespace std;

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

int v[152][152];
vector<int> key[22501];
bool pd[22501];
int viz[152][152];
int n, m, k;
struct Coord {
    int i, j;
} q[22501];
int di[4] = {0, -1, 0, 1};
int dj[4] = {-1, 0, 1, 0};

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

int foo(int i, int j) {
    int l = 0, r = 0, ii, jj, e, rez = 1;
    q[r].i = i;
    q[r++].j = j;
    viz[i][j] = 2;
    while(l < r) {
        i = q[l].i;
        j = q[l++].j;
        e = (i - 1) * m + j;
        for(const int el : key[e]) {
            int x = el / m + 1, y = (el - 1) % m + 1;
            if(viz[x][y] != 2) {
                rez++;
                viz[x][y] = 2;
                q[r].i = x;
                q[r++].j = y;
                pd[el] = true;
            }
        }
        for(int k = 0; k < 4; k++) {
            ii = i + di[k];
            jj = j + dj[k];
            if(ii >= 1 && jj >= 1 && ii <= n && jj <= m && viz[ii][jj] != 2)
            if(pd[v[ii][jj]]) {
                rez++;
                q[r].i = ii;
                q[r++].j = jj;
                viz[ii][jj] = 2;
                pd[(ii - 1) * m + jj] = true;
            }
            else if(!viz[ii][jj]) {
                key[v[ii][jj]].push_back((ii - 1) * m + jj);
                viz[ii][jj] = 1;
            }
        }
    }
    return rez;
}

int main() {
    inf >> n >> m >> k;
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= m; j++) {
            inf >> v[i][j];
        }
    }
    for(int i = 0; i <= n + 1; i++) {
        viz[i][0] = 4;
        viz[i][m + 1] = 4;
    }
    for(int j = 0; j <= m + 1; j++) {
        viz[0][j] = 4;
        viz[n + 1][j] = 4;
    }
    pd[k] = true;
    outf << foo(k / m + 1, (k - 1) % m + 1) << '\n';
    return 0;
}