Cod sursa(job #363068)

Utilizator tamas_iuliaTamas Iulia tamas_iulia Data 11 noiembrie 2009 18:38:22
Problema Castel Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.44 kb
#include <stdio.h>
#define Nmax 252

const int dx[4]={-1,0,1,0}, dy[4]={0,1,0,-1};
struct punct{ int x,y; } Q[Nmax*Nmax+2];
int a[Nmax][Nmax],marc[Nmax][Nmax],inq[Nmax][Nmax],mv[Nmax][Nmax],viz[Nmax][Nmax];
int amc[Nmax*Nmax+2];
int n,m,i,j,k,nr,ok;
int p,u,xi,yi,xx,yy,ce_cheie;

int main(){
	freopen("castel.in","r",stdin);
   freopen("castel.out","w",stdout);
   scanf("%d%d%d",&n,&m,&k);
   xi=k/m +1; yi=k % m; if(yi==0) yi=m, xi--;
   for(i=1;i<=n;++i)
     for(j=1;j<=m;++j) scanf("%d",&a[i][j]);

   mv[1][1]=mv[1][m]=mv[n][1]=mv[n][m]=2;
   for(i=2;i<=m-1;++i) mv[1][i]=mv[n][i]=3;
   for(i=2;i<=n-1;++i) mv[i][1]=mv[i][m]=3;
   for(i=2;i<n;++i)
     for(j=2;j<m;++j) mv[i][j]=4;
   Q[1].x=xi; Q[1].y=yi; u=1;
   amc[k]=1;
   marc[xi][yi]=1;

   do{
   	ok=0;
   	for(i=1;i<=u;++i)
      if( viz[Q[i].x][Q[i].y] < mv[Q[i].x][Q[i].y] )
   	  for(k=0;k<4;++k){
          	xx=Q[i].x+dx[k];
            yy=Q[i].y+dy[k];
            if( xx>0 && yy>0 && xx<=n && yy<=m && amc[ a[xx][yy] ])
         		if(!marc[xx][yy]){
               	Q[++u].x=xx; Q[u].y=yy;
                  marc[xx][yy]=1;
           	    	ce_cheie = (xx-1)*m + (yy%m > 0 ? yy%m : m);
           	   	amc[ce_cheie]=1;
                  ok=1;
                  viz[Q[i].x][Q[i].y]++;
					}
        }
   } while(ok);

   for(i=1;i<=n;++i)
     for(j=1;j<=m;++j) nr+=marc[i][j];

   printf("%d\n",nr);
   fclose(stdin); fclose(stdout);
   return 0;
}