Cod sursa(job #429366)

Utilizator AndrewTheGreatAndrei Alexandrescu AndrewTheGreat Data 30 martie 2010 02:10:01
Problema Castel Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.36 kb
#include <iostream>
#include <vector>

using namespace std;

#define N_MAX 151
#define IN "castel.in"
#define OUT "castel.out"

int viz[N_MAX][N_MAX],A[N_MAX][N_MAX];
int key[N_MAX*N_MAX],coada[N_MAX*N_MAX];
vector <int> key_poate[N_MAX*N_MAX];
vector <int>::iterator it;

int di[4]={-1,0,0,1},
    dj[4]={0,-1,1,0};

int main ()
{
    freopen (IN,"r",stdin);
    freopen (OUT,"w",stdout);

    int M,N,K,pq,uq,Res=0,n,i,j,ii,jj;

    scanf("%d %d %d",&M,&N,&K);
    for(int i=0;i<M;i++)
        for(int j=0;j<N;j++)
        {
            scanf("%d",&A[i][j]);
			A[i][j]--;
        }

    coada[pq=uq=0]=--K;
    viz[K/N][K%N]=1;
    for(;pq<=uq;pq++)
    {
        key[n=coada[pq]]=1,Res++;
        for(it=key_poate[n].begin();it!=key_poate[n].end();it++)
            if(!viz[*it/N][*it%N])
            {
                coada[++uq]=*it;
                viz[*it/N][*it%N]=1;
            }
        i=n/N;
        j=n%N;
        for(int d=0;d<4;d++)
        {
            ii=i+di[d];
            jj=j+dj[d];
            if(ii < 0 || jj < 0 || ii >= M || jj >= N || viz[ii][jj]) continue;
            if(key[A[ii][jj]])
            {
                coada[++uq]=ii*N+jj;
                viz[ii][jj]=1;
            }
            else key_poate[A[ii][jj]].push_back(ii*N+jj);
        }
    }
    printf("%d\n",Res);
    return 0;
}