Cod sursa(job #1067001)

Utilizator dariusdariusMarian Darius dariusdarius Data 25 decembrie 2013 22:57:01
Problema Castel Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.28 kb
#include<cstdio>
#include<vector>
using namespace std;
int dx[]={-1,1,0,0};
int dy[]={0,0,-1,1};
int Res,N,M,K,a[155][155];
int Q[150*150+5];
bool viz[155][155];
int key[150*150+5];
vector<int> key_list[150*150+5];
int main()
{
    freopen("castel.in","r",stdin);
    freopen("castel.out","w",stdout);
    scanf("%d%d%d",&N,&M,&K);
    for(int i=0;i<N;i++)
        for(int j=0;j<M;j++)
        {
            scanf("%d",&a[i][j]);
            a[i][j]--;
        }
    int p=0,u=0;K--;
    Q[u]=K;
    viz[K/M][K%M] = 1;
    while(p<=u)
    {
        int n=Q[p];
        key[Q[p]]=1;Res++;
        for(vector<int>::iterator it=key_list[n].begin();it!=key_list[n].end();it++)
            if(!viz[*it/M][*it%M])
            {
                Q[++u]=*it;
                viz[*it/M][*it%M]=1;
            }
        int x=n/M,y=n%M;
        for(int d=0;d<4;d++)
        {
            int xn=x+dx[d],yn=y+dy[d];
            if(xn<0 || yn<0 || xn>=N || yn>=M || viz[xn][yn])
                continue;
            if(key[a[xn][yn]])
            {
                Q[++u]=xn*M+yn;
                viz[xn][yn]=1;
            }
            else
                key_list[a[xn][yn]].push_back(xn*M+yn);
        }
        p++;
    }
    printf("%d\n",Res);
    return 0;
}