Cod sursa(job #59794)

Utilizator ViksenVictor-Nicolae Savu Viksen Data 10 mai 2007 15:45:25
Problema Castel Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.69 kb
#include <stdio.h>

struct point { int v ; point *l ; } *S[22501];
struct camera { int x,y; } Q[2][22501];
int n,m,i,c,lQ[3],U[22501],A[151][151],pp[22501],d[4][2]={{-1,0},{1,0},{0,-1},{0,1}};

void ReadData ()
{
 	int k,i,j;
 	freopen ( "castel.in" , "r" , stdin );
    scanf ( "%d %d %d" , &n , &m , &k );
    for ( i=1 ; i<=n ; i++ )
       for ( j=1 ; j<=m ; j++ )
       		scanf ( "%d" , &A[i][j] );
    U[k]=1; Q[0][0].x=(k/m)+1; Q[0][0].y=(k-1)%m+1; lQ[0]=1;
}

void WriteData ()
{
    freopen ( "castel.out" , "w" , stdout );
 	printf ( "%d\n" , c );
    fclose ( stdout );
}

void InsertPoint ( int poz , int valoare )
{
 	point *p=new point;
    p->l=S[poz];
    p->v=valoare;
    S[poz]=p;
}

void Viziteaza ( camera cam , int p )
{
 	int x,y,r,i;
    for ( i=0 ; i<4 ; i++ ) {
       x=cam.x+d[i][0];
       y=cam.y+d[i][1];
       r=(x-1)*m+y;
       if ( (x>0)&&(y>0)&&(x<=n)&&(y<=m)&&!U[r] )
         if ( U[A[x][y]] ) {
           Q[!p][lQ[!p]].x=x;
           Q[!p][lQ[!p]].y=y;
           lQ[!p]++;
           U[r]=1;
         } else if (!pp[r]) { InsertPoint ( A[x][y] , r );pp[r]=1;}
    }
	r=(cam.x-1)*m+cam.y;
	point *q;
    for ( ; S[r] ; ) {
       if (!U[S[r]->v])  {
         Q[!p][lQ[!p]].x=(S[r]->v/m)+1;
         Q[!p][lQ[!p]].y=(S[r]->v-1)%m+1;
         U[S[r]->v]=1;
         lQ[!p]++;
       }
       q=S[r];
       S[r]=S[r]->l;
       delete (q);
    }    
}

void Solve ()
{
 	for ( c=0,i=0 ; lQ[i] ; i=!i ) {
       c+=lQ[i];
       for ( lQ[i]-- ; lQ[i]+1 ; lQ[i]-- )
           Viziteaza ( Q[i][lQ[i]] , i );
       lQ[i]=0;
    }
}

int main ()
{
 	ReadData ();
    Solve ();
    WriteData ();
    return 0;
}