Cod sursa(job #1326829)

Utilizator TarabanDragosTaraban Dragos-Petru TarabanDragos Data 26 ianuarie 2015 01:46:01
Problema Castel Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.47 kb
#include<cstdio>
#include<vector>
#include<queue>
using namespace std;
queue<int>q;
vector<int>L[1000000];
int di[4]={0,1,0,-1};
int dj[4]={1,0,-1,0};
int n,m,k,a,b,i,j,ic,jc,iv,jv,nr,nrt,x[500][500],v[500][500],z[500][500],y[2][1100000],d[1100000];
FILE *f,*g;
int main(){
    f=fopen("castel.in","r");
    g=fopen("castel.out","w");
    fscanf(f,"%d%d%d",&n,&m,&k);
    for(i=1;i<=n;i++){
        for(j=1;j<=m;j++){
            fscanf(f,"%d",&x[i][j]);
            z[i][j]=++nrt;
            y[0][nrt]=i;
            y[1][nrt]=j;
            if(nrt==k){
                ic=i;
                jc=j;
            }
        }
    }
    q.push(k);
    v[ic][jc]=1;
    while(!q.empty()){
        nr++;
        a=q.front();
        q.pop();
        d[a]=1;
        for(i=0;i<L[a].size();i++){
            b=L[a][i];
            if(v[ y[0][b] ][ y[1][b] ]==0){
                v[ y[0][b] ][ y[1][b] ]=1;
                q.push(b);
            }
        }
        ic=y[0][a];
        jc=y[1][a];
        for(j=0;j<4;j++){
            iv=ic+di[j];
            jv=jc+dj[j];
            b=z[iv][jv];
            if(iv>=1&&iv<=n&&jv>=1&&jv<=n&&v[iv][jv]==0){
                if(d[ x[iv][jv] ]!=0){
                    q.push(b);
                    v[iv][jv]=1;
                }
                else
                    L[ x[iv][jv] ].push_back(b);
            }
        }
    }
    fprintf(g,"%d",nr);

    fclose(f);
    fclose(g);
    return 0;
}