Cod sursa(job #2469263)

Utilizator andreiomd1Onut Andrei andreiomd1 Data 6 octombrie 2019 17:55:20
Problema Castel Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.18 kb
#include <fstream>
#include <queue>
#include <vector>

using namespace std;

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

const int NMAX = 155;

int N, M, K, Need[NMAX][NMAX];

bool Have[NMAX * NMAX];

int dp[NMAX][NMAX];

queue < pair < int, int > > Q;

vector < pair < int, int > > Remaining[NMAX * NMAX];

int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, 1, 0, -1};

static inline int Room (int X, int Y)
{
    return (X - 1) * M + Y;
}

static inline pair < int, int > Key (int Nr)
{
    if(Nr % M == 0)
        return {Nr / M, M};

    return {Nr / M + 1, Nr % M};
}

static inline void Read ()
{
    f.tie(NULL);

    f >> N >> M >> K;

    for(int i = 1; i <= N; ++i)
        for(int j = 1; j <= M; ++j)
            f >> Need[i][j];

    return;
}

static inline void Write ()
{
    int ans = 0;

    for(int i = 1; i <= N; ++i)
        for(int j = 1; j <= M; ++j)
            if(dp[i][j])
                ++ans;

    g << ans << '\n';

    return;
}

static inline void Check (int X, int Y)
{
    for(auto it : Remaining[Room(X, Y)])
        if(!dp[it.first][it.second])
        {
            dp[it.first][it.second] = 1;

            Q.push({it.first, it.second});
        }

    return;
}

static inline void Solve ()
{
    dp[Key(K).first][Key(K).second] = 1;
    Have[K] = 1;

    Q.push({Key(K).first, Key(K).second});

    while(!Q.empty())
    {
        int X = Q.front().first;
        int Y = Q.front().second;

        Check(X, Y);

        for(int i = 0; i < 4; ++i)
        {
            int XX = X + dx[i];
            int YY = Y + dy[i];

            if(XX < 1 || XX > N || YY < 1 || YY > M)
                continue;

            if(!Have[Need[XX][YY]])
            {
                Remaining[Need[XX][YY]].push_back({XX, YY});

                continue;
            }

            Have[Room(XX, YY)] = true;

            if(!dp[XX][YY])
            {
                dp[XX][YY] = 1;

                Q.push({XX, YY});
            }
        }

        Check(X, Y);

        Q.pop();
    }

    return;
}

int main()
{
    Read();

    Solve();

    Write();

    return 0;
}