Cod sursa(job #56450)

Utilizator raula_sanChis Raoul raula_san Data 29 aprilie 2007 16:35:47
Problema Castel Scor 60
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.09 kb
#include <cstdio>

#define dim 151

int N, M, K, SOL, sfC;
int S[dim*dim], A[dim][dim], Viz[dim][dim], Cx[dim*dim], Cy[dim*dim];

struct nod
{
       int x, y;
       nod *next;
} *L, *EL;

void Read();
void Solve();
void Write();

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

void key_to_pos(int &x, int &y, int k)
{
     y = k % M;
     x = k / M;
     
     if(!y)
           y = M;
     else
         ++ x;
}

int pos_to_key(int x, int y)
{
    return ((x-1) * M) + y;
}

int main()
{
    Read();
    Solve();
    Write();
    
    return 0;
}

void Read()
{
     freopen("castel.in", "r", stdin);
     
     scanf("%d %d %d", &N, &M, &K);
     
     int i, j;
     
     for(i=1; i<=N; ++i)
              for(j=1; j<=M; ++j)
                       scanf("%d", &A[i][j]);
                       
     fclose(stdin);
}

void Solve()
{
     L = new nod;
     
     key_to_pos(L->x, L->y, K);
     S[K] = 1;
     Viz[L->x][L->y] = 1;
     
     L -> next = NULL;
     EL = L;
     
     int changes = 1, i, j, x, y;
     
     while(L)
     {
         changes = 0;
         
         while(L)
         {
             for(i=0; i<4; ++i)
             {
                 x = L -> x + dx[i];
                 y = L -> y + dy[i];
                 
				 if( x>=1 && x<=N && y>=1 && y<=M && Viz[x][y] != 1 )
                 {
                     if(S[A[x][y]])
                     {
                         S[pos_to_key(x, y)] = 1;
                         Viz[x][y] = 1;
                         
                         nod *p = new nod;
                         p -> x = x;
                         p -> y = y;
                         p -> next = NULL;
                         EL -> next = p;
                         EL = p;
                     }
                     
					 else if(!Viz[x][y])
                     {
						 Viz[x][y] = 2;

                         ++ sfC;
                         Cx[sfC] = x;
						 Cy[sfC] = y;
                     }
                 }
			 }

			 nod *p = L;
			 L = L -> next;
			 delete p;
         }
         
         L = EL = NULL;
         
         int ns;
         
         for(i=1, ns=0; i<=sfC; ++i)
		 {
				 if(S[A[Cx[i]][Cy[i]]] && Viz[Cx[i]][Cy[i]] != 1)
				 {
					 changes = 1;
					 S[pos_to_key(Cx[i], Cy[i])] = 1;
					 Viz[Cx[i]][Cy[i]] = 1;

					 nod *p = new nod;
					 p -> x = Cx[i];
					 p -> y = Cy[i];
					 p -> next = NULL;

					 if(L != NULL)
					 {
						  EL -> next = p;
						  EL = p;
					 }
                     else
                         L = EL = p;
                 }
                 else
                 {
                     ++ ns;
                     Cx[ns] = Cx[i];
                     Cy[ns] = Cy[i];
                 }
         }
         
         sfC = ns;
     }
     
     for(i=1; i<=N; ++i)
              for(j=1; j<=M; ++j)
					   SOL += Viz[i][j] == 1;
}

void Write()
{
     freopen("castel.out", "w", stdout);
     
     printf("%d", SOL);
     
     fclose(stdout);
}