Cod sursa(job #2633500)

Utilizator FrostfireMagirescu Tudor Frostfire Data 7 iulie 2020 16:39:27
Problema Castel Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.72 kb
#include <iostream>
#include <fstream>
#include <queue>
#define NMAX 150

using namespace std;

ifstream f("castel.in");
ofstream g("castel.out");

int n, m, k, v[NMAX+10][NMAX+10];
int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, 1, 0, -1};
bool used[NMAX*NMAX+10], viz[NMAX+10][NMAX+10];
queue <pair <int, int> > Q, Keys[NMAX*NMAX+10];

pair <int, int> key(int ke)
{   pair <int, int> x;
    x.first = (ke - 1) / m + 1;
    if(ke % m == 0) x.second = m;
    else x.second = ke % m;
    return x;
}

void unlock(int ke)
{   if(used[ke]) return;
    used[ke] = 1;
    while(!Keys[ke].empty())
        {   pair <int, int> a = Keys[ke].front();
            Keys[ke].pop();
            viz[a.first][a.second] = 1;
            Q.push(a);
        }
}

int Lee()
{   pair <int, int> coord = key(k);
    viz[coord.first][coord.second] = 1;
    Q.push(coord);
    int ans = 0;
    while(!Q.empty())
        {   ans++;
            pair <int, int> a = Q.front();
            Q.pop();
            for(int t=0; t<4; t++)
                {   pair <int, int> vec = {a.first+dx[t], a.second+dy[t]};
                    if(vec.first && vec.first <= n && vec.second && vec.second <= m
                       && !viz[vec.first][vec.second])
                        {   if(used[v[vec.first][vec.second]]) Q.push(vec);
                            else Keys[v[vec.first][vec.second]].push(vec);
                            viz[vec.first][vec.second] = 1;
                        }
                }
            unlock((a.first - 1) * m + a.second);
        }
    return ans;
}

int main()
{
    f >> n >> m >> k;
    for(int i=1; i<=n; i++)
        for(int j=1; j<=m; j++) f >> v[i][j];
    g << Lee() << '\n';
    return 0;
}