Cod sursa(job #160820)

Utilizator pascu_iulianPascu Iulian pascu_iulian Data 16 martie 2008 22:32:07
Problema Castel Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.9 kb

#include<iostream.h>
#include<fstream.h>

ifstream fin("castel.in");
ofstream fout("castel.out");

    // varianta recursiva
    
bool chei[22801]={0};            //cheile detinute
long cam[151][151],camere=1;     // camerele
int m,n;
int  cx[22801],cy[22801];       // aici pastram coordonatele camerelor vecine cu cele deschise aka coadale
int sp=0;   // pt coada....



void vecini(int x,int y)           // adaoga vecini inchisi la coada
{int adx[4]={-1,0,1,0};
int ady[4]={0,1,0,-1};
for(int i=0;i<4;i++)
   {   int nx,ny; 
       nx=x+adx[i];
       ny=y+ady[i];
       if(nx>0 && nx<=m)
       if(ny>0 && ny<n)
         {  int c=n*(x-1)+y;
            if( chei[c]==0 )       // if camera e inchisa
              { sp++;             // adaugam camera la black list aka bl
                cx[sp]=nx;
                cx[sp]=ny;
              }
         } 
   }
}

int main()
{
int i,j;
long poz;        
fin>>m>>n>>poz;     //citim datele
for(i=1;i<=m;i++)
for(j=1;j<=n;j++)
  fin>>cam[i][j]; 
chei[poz]=1;    //avem prima cheie
int x,y;        //aflam coordonatele camerei initiale   
if(poz%n==0) 
 { x=poz/n; y=n; }
 else
 { x=poz/n+1; y=poz%n; }
vecini(x,y);
int g=1;
while(g==1)
 {g=0;
  for(i=1;i<=sp;i++)          // cercetam camerele vecine cu cele deja deschise
    { x=cx[i];
      y=cy[i];
      int cc=cam[x][y];
      if ( chei[cc]==1 )       // daca gasim o camera deschisa
        { int c=n*(x-1)+y;    
          chei[c]=1;                     // adaugam cheia la breloc
          vecini(x,y);                   // adaugam vecinii inchisi la coada
          cx[i]=cx[sp];            //  \
          cy[i]=cy[sp];            //   \
          sp--;                    //    -- > mutam ultimul el in poz curenta
          i--;                     //   /
          camere++;
          g=1;
        }
    }
  }
fout<<camere;
fout.close();
return 0;
}