Cod sursa(job #1698708)

Utilizator sucureiSucureiRobert sucurei Data 5 mai 2016 08:09:17
Problema Castel Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.82 kb
#include <fstream>
#include <queue>
#include <vector>
#define x first
#define y second
using namespace std;
ifstream fin ("castel.in");
ofstream fout ("castel.out");
const int dl[] = { -1, 0, 1, 0 };
const int dc[] = { 0, 1, 0, -1 };
int N, M, K, X, Y, sol, V[160][160];
int B[22510], fr[160][160];
vector < pair < int, int > > A[22510];

queue < pair < int, int > > Q;

void Pune_In_Coada()
{
    for (int i = 0; i < A[K].size(); i++)
    {
        X = A[K][i].x;
        Y = A[K][i].y;
        for (int k = 0; k < 4; k++)
        {
            int ii = X + dl[k];
            int jj = Y + dc[k];
            if (fr[ii][jj] == 1)
            {
                Q.push(make_pair(X, Y));
            }
        }
    }
}

int main()
{
    fin >> N >> M >> K;
    for (int i = 1; i <= N; i++)
    {
        for (int j = 1; j <= M; j++)
        {
            fin >> V[i][j];
            A[V[i][j]].push_back(make_pair(i, j));
        }
    }
    for (int i = 0; i <= N + 1; i++) fr[i][0] = fr[i][M+1] = 2;
    for (int j = 0; j <= M + 1; j++) fr[0][j] = fr[N+1][j] = 2;
    X = (K - 1) / M + 1;
    Y = K % M;
    if (!Y) Y = M;

    Q.push(make_pair(X, Y));
    while (!Q.empty())
    {
        int i = Q.front().x;
        int j = Q.front().y;
        Q.pop();
        K = (i - 1) * M + j;

        if (!B[K])
        {
            Pune_In_Coada();
            B[K] = 1;
        }
        fr[i][j] = 1;

        for (int k = 0; k < 4; k++)
        {
            int ii = i + dl[k];
            int jj = j + dc[k];
            if (!fr[ii][jj] && B[V[ii][jj]])
            {
                Q.push(make_pair(ii, jj));
            }
        }
    }

    for (int i = 1; i <= 22500; i++)
    {
        if (B[i]) sol++;
    }

    fout << sol << '\n';
    fout.close();
    return 0;
}