Cod sursa(job #3185863)

Utilizator AlexPlesescuAlexPlesescu AlexPlesescu Data 20 decembrie 2023 18:10:54
Problema Castel Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.01 kb
#include <bits/stdc++.h>

#define int long long int
#define cin fin
#define cout fout

using namespace std;

ifstream cin("castel.in");
ofstream cout("castel.out");

struct tip {
    int x;
    int y;
};

const int NMAX = 155;

queue<pair<int,int>> Q;
vector<tip> chei[NMAX*NMAX+100];
int n,m,k,a[NMAX][NMAX],b[NMAX][NMAX],viz[NMAX][NMAX],dx[]= {-1,0,1,0},dy[]= {0,1,0,-1},ans;

inline bool inmat(int i,int j) {
    return i >= 1 and i <= n and j >= 1 and j <= m;
}

signed main() {
    cin >> n >> m >> k;
    map<int,bool> M;
    int nr = 0;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++) {
            cin >> a[i][j];
            nr++;
            b[i][j] = nr;
            if (nr == k && a[i][j] == b[i][j]) {
                Q.push({i, j});
                viz[i][j] = 1;
                M[nr] = 1;
            }
        }
    while (!Q.empty()) {
        int i = Q.front().first;
        int j = Q.front().second;
        viz[i][j] = 1;
        M[b[i][j]] = 1;
        int cheie = b[i][j];
        for (int i=0; i < chei[cheie].size(); i++) {
            if (!viz[chei[cheie][i].x][chei[cheie][i].y]) {
                /// pot sa o deschid
                Q.push({chei[cheie][i].x,chei[cheie][i].y});
                viz[chei[cheie][i].x][chei[cheie][i].y] = 1;
                int primesc = b[chei[cheie][i].x][chei[cheie][i].y];
                M[primesc] = 1;
            }
        }
        Q.pop();
        for (int k=0; k < 4; k++) {
            int ii = i + dx[k];
            int jj = j + dy[k];
            if (inmat(ii,jj) && !viz[ii][jj] && M[a[ii][jj]]) {
                Q.push({ii,jj});
                viz[ii][jj] = 1;
            }
            else if (inmat(ii,jj) && !viz[ii][jj] && !M[a[ii][jj]]) {
                chei[a[ii][jj]].push_back({ii,jj});
            }
        }
    }
    for (int i=1; i <= n; i++)
        for (int j=1; j <= m; j++)
            if (viz[i][j])
                ans++;
    cout << ans;
    return 0;
}