Cod sursa(job #901198)

Utilizator AlexandruValeanuAlexandru Valeanu AlexandruValeanu Data 1 martie 2013 08:13:03
Problema Castel Scor 100
Compilator cpp Status done
Runda simulare_10 Marime 1.42 kb
#include <cstdio>
#include <vector>
#include <queue>

#define Nmax 152

using namespace std;

const int dl[] = {-1,0, 1, 0};
const int dc[] = { 0, 1,0,-1};

int n, m , k, nr = 0;

int mat[Nmax][Nmax];
bool viz[Nmax][Nmax];
bool chei[Nmax*Nmax];

vector <int> lista[Nmax*Nmax];
queue <int> Q;

void citire(){

    freopen("castel.in", "r", stdin);

    scanf("%d %d %d", &n, &m, &k);

    for(int i = 0; i < n; i++)
        for(int j = 0; j < m; j++)
            scanf("%d", mat[i]+j),
            mat[i][j]--;
}

void lee(){

    vector <int>::iterator it;

    Q.push(--k);
    viz[k/m][k%m] = 1;

    while(!Q.empty()){

        int current = Q.front();
        Q.pop();
        chei[current] = 1;
        nr++;

        for(it = lista[current].begin(); it != lista[current].end(); it++)
            if(!viz[*it/m][*it%m])
                Q.push(*it),
                viz[*it/m][*it%m] = 1;

        int i = current/m, j = current%m;

        for(int l=0; l<4; l++){

            int i2 = i + dl[l], j2 = j + dc[l];

            if(i2 < 0 || j2 < 0 || i2 >= n || j2 >= m || viz[i2][j2])
                continue;

            if(chei[mat[i2][j2]])
                Q.push(i2*m+j2),
                viz[i2][j2] = 1;
            else
                lista[mat[i2][j2]].push_back(i2*m+j2);
        }
    }
}

void afis(){

    freopen("castel.out", "w", stdout);

    printf("%d\n", nr);
}

int main()
{

    citire();
    lee();
    afis();

    return 0;
}