Cod sursa(job #501555)

Utilizator S7012MYPetru Trimbitas S7012MY Data 15 noiembrie 2010 18:32:14
Problema Castel Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.22 kb
#include <stdio.h>
#include <vector>
#define DN 180
using namespace std;

const int di[]={-1,1, 0, 0};
const int dj[]={ 0, 0,-1,1};
int N, M, K, A[DN][DN], coada[DN*DN], rez;
char v[DN][DN], key[DN*DN];
vector<int> lsc[DN*DN];

int main()
{
    int n, i, j, d, ii, jj, ql, qr;
    freopen("castel.in", "r", stdin);
    freopen("castel.out", "w", stdout);
    scanf("%d %d %d", &N, &M, &K);
    for (i=0; i < N; i++)
        for (j=0; j < M; j++) {
            scanf("%d", A[i]+j);
            --A[i][j];
        }
    coada[ql=qr=0]=--K;
    v[K/M][K%M]=1;
    for (; ql <= qr; ql++){
        key[n=coada[ql]]=1; ++rez;
        for (vector<int>::iterator it=lsc[n].begin(); it != lsc[n].end(); it++)
            if (!v[*it/M][*it%M]){
                coada[++qr]=*it;
                v[*it/M][*it%M]=1;
            }
        i=n/M; j=n%M;
        for (d=0; d < 4; d++){
            ii=i+di[d], jj=j+dj[d];
            if (ii < 0 || jj < 0 || ii >= N || jj >= M || v[ii][jj]) continue;
            if (key[A[ii][jj]]){
                coada[++qr]=ii*M+jj;
                v[ii][jj]=1;
            }
            else lsc[A[ii][jj]].push_back(ii*M+jj);
        }
    }
    printf("%d", rez);
    return 0;
}