Cod sursa(job #1704464)

Utilizator emanuel_rRamneantu Emanuel emanuel_r Data 18 mai 2016 20:41:05
Problema Castel Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.71 kb
#include<iostream>
#include<fstream>
#include<vector>
#include<iterator>
#include<queue>

using namespace std;

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

int const NMax = 155;
int M[NMax][NMax], A[NMax][NMax], Open[NMax][NMax], InQ[NMax * NMax];
queue <int> QK;
vector <pair <int, int> > G[NMax * NMax];
int k, n, m, sol;
int x[] = {0, 0, -1, 1}, y[] = {1, -1, 0, 0};

void Read()
{
    int i, j, key;

    f>>n>>m>>k;
    for(i=1; i<=n; i++)
        for(j=1; j<=m; j++){
            f>>key;
            G[key].push_back(make_pair(i, j));
        }
}

void Fill(int i, int j)
{
    int ivec, jvec;

    M[i][j] = 2;

    if(!InQ[(i-1) * m + j]){
        QK.push((i-1) * m + j);
        InQ[(i-1) * m + j] = 1;
    }

    for(int k=0; k<4; k++){
        ivec = i + x[k];
        jvec = j + y[k];
        if(ivec < 1 || jvec < 1 || ivec > n || jvec > m)
            continue;

        if(M[ivec][jvec] == 0)
            M[ivec][jvec] = 1;
        if(Open[ivec][jvec] && M[ivec][jvec] != 2)
            Fill(ivec, jvec);
    }
}

void Bell()
{
    int i, j, xst, yst, x, y, key;

    yst = ((k-1) % m) + 1;
    xst = (k-1)/m + 1;
    QK.push(k);
    InQ[k] = 1;
    Open[xst][yst] = 1;
    Fill(xst, yst);

    while(QK.size()){
        key = QK.front();
        QK.pop();

        for(i=0; i<G[key].size(); i++){
            x = G[key][i].first;
            y = G[key][i].second;
            Open[x][y] = 1;
            if(M[x][y])
                Fill(x, y);
        }
    }

    for(i=1; i<=n; i++)
        for(j=1; j<=m; j++)
            if(M[i][j] == 2)
                sol++;

    g<<sol<<"\n";
}

int main()
{
    Read();
    Bell();
    return 0;
}