Cod sursa(job #193175)

Utilizator alexeiIacob Radu alexei Data 2 iunie 2008 20:30:58
Problema Castel Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.15 kb
#include<stdio.h>
#include<vector>
#define nmax 22524
#define limit 152
using namespace std;

const int dx[]={ 1, 0, -1, 0};
const int dy[]={ 0, 1,  0,-1};

vector < int > key[nmax];

int a[ limit ][ limit ];
int queue[nmax];
bool uz[ limit ][ limit ];
bool marked[nmax];

int main()
{
 freopen("castel.in","r",stdin);
 freopen("castel.out","w",stdout);
 
 int N,M,K;
 scanf("%d%d%d",&N,&M,&K);   
    
   int i=0,j=0; 
   int aux1,aux2,aux; 
   int aux3,aux4;
   
   for( i=0; i<N; ++i)
    for( j=0; j<M; ++j )
    {
         scanf("%d",&a[i][j]);
         uz[i][j]=false;
         --a[i][j];
    }
   //daca ai sti la ce puteam sa gresesc, tot nu m-ai crede 
   --K;
   
   uz[ K/M ][ K%M ]=true;   
   
   int incr=1,sf=1;
   
   queue[1]=K;
   
   vector< int >::iterator it;   
   
   int solfin=0;
   
   while( incr<=sf )
   {      //printf("%d ",queue[incr]);
          aux=queue[incr++];
          //printf("(%d)aux ");
          ++solfin;
          marked[ aux ]=true; 
          
          for(it=key[aux].begin(); it!=key[aux].end(); ++it)
          {
           aux1=*it/M;
           aux2=*it%M;
           
           if( uz[aux1][aux2]==false )
           {
               queue[ ++sf ]=*it;
               uz[aux1][aux2]=true;
           }
          } 
         
         aux1=aux/M;
         aux2=aux%M;
         //printf("( (%d %d) %d)\n",aux1,aux2,aux);
         for(i=0; i<4; ++i)
         {  
         aux3=aux1+dx[i];
         aux4=aux2+dy[i];
         
         if( aux3>=0 && aux3< N && aux4>=0 && aux4< M )
             if( uz[ aux3 ][ aux4 ]==false )
                 if( marked[ a[aux3][aux4] ]==true )
                 {
                 queue[ ++sf ]=aux3*M+aux4;
                 //     if( queue[sf]==9 )
                 //     printf("  (aux3 %d aux4 %d aux1 %d aux2 %d aux %d a[aux3][aux4]%d)  ",aux3,aux4,aux1,aux2,aux,a[aux3][aux4]);
                 uz[aux3][aux4]=true;
                 }                
                 else
                 key[ a[aux3][aux4] ].push_back(aux3*M+aux4);        
         }
   }
   
   printf("%d\n",solfin); 
    
    
    return 0;
}