Cod sursa(job #160817)

Utilizator pascu_iulianPascu Iulian pascu_iulian Data 16 martie 2008 22:17:36
Problema Castel Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.85 kb
// #include<conio.h>
#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
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];
      if ( chei[ cam[x][y] ]==1 )       // daca gasim o camera deschisa
        {int c=n*(x-1)+y;    
         chei[c]=1;                     // adaugam cheia la breloc
         vecini(x,y); 
         cx[i]=cx[sp];            //  \
         cy[i]=cy[sp];            //   \
         sp--;                    //    -- > mutam ultimul el in poz curenta
         i--;                     //   /
         camere++;
         g=1;
        }
    }
  }
fout<<camere;
fout.close();
// getch();
return 0;
}