Cod sursa(job #2559253)

Utilizator Alex_BubBuburuzan Alexandru Alex_Bub Data 27 februarie 2020 10:21:44
Problema Castel Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.43 kb
#include <fstream>
#include <vector>

using namespace std;

ifstream fin("castel.in");
ofstream fout("castel.out");

const int NMax = 150, PMax = 150 * 150;

int Key[NMax + 5][NMax + 5], N, M, K, dl[4] = {-1, 0, 1, 0}, dc[4] = {0, 1, 0, -1}, A[NMax + 5][NMax + 5], Sol;
vector <int> Request[PMax + 5];
pair<int, int> Coord[PMax + 5];
bool Use[PMax + 5], Have[PMax + 5];

inline bool Valid(int i, int j)
{
    return i && j && i <= N && j <= M;
}

void Solve(int Room)
{
    Have[Room] = Use[Room] = true;
    int l = Coord[Room].first, c = Coord[Room].second, nl, nc, NewRoom;

    for(int t = 0; t < 4; t++)
    {
        nl = l + dl[t], nc = c + dc[t];
        NewRoom = (nl - 1) * M + nc;

        if(Use[NewRoom] || !Valid(nl, nc)) continue;
        Use[NewRoom] = true;

        if(Have[A[nl][nc]])
            Solve(NewRoom);
        else
            Request[A[nl][nc]].push_back(NewRoom);
    }

    while(!Request[Room].empty())
    {
        int x = Request[Room].back();
        Request[Room].pop_back();
        Solve(x);
    }
}

int main()
{
    fin >> N >> M >> K;

    for(int i = 1, ct = 0; i <= N; i++)
        for(int j = 1; j <= M; j++)
        {
            fin >> A[i][j];
            Coord[++ct] = {i, j};
        }
    Solve(K);

    for(int i = 1; i <= N * M; i++)
        Sol += Have[i];

    fout << Sol << '\n';

    fin.close();
    fout.close();

    return 0;
}