Cod sursa(job #3185856)

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

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

using namespace std;

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

queue<pair<int,int>> Q;
set<pair<int,int>> lista;
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()) {
        bool ok = 0;
        int i = Q.front().first;
        int j = Q.front().second;
        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]] == 1) {
                Q.push({ii, jj});
                M[b[ii][jj]] = 1;
                viz[ii][jj] = 1;
                ok = 1;
            } else if (inmat(ii, jj) && !viz[ii][jj] && !M[a[ii][jj]]) {
                lista.insert({ii,jj});
            }
        }
        if (ok) {
            for (auto it : lista) {
                if (!viz[it.first][it.second] && M[a[it.first][it.second]] == 1) {
                    Q.push({it.first,it.second});
                    viz[it.first][it.second] = 1;
                    M[b[it.first][it.second]] = 1;
                    lista.erase({it.first,it.second});
                }
            }
        }
    }
    for (int i=1; i <= n; i++)
        for (int j=1; j <= m; j++)
            if (viz[i][j])
                ans++;
    cout << ans;
    return 0;
}