Cod sursa(job #598866)

Utilizator Smaug-Andrei C. Smaug- Data 27 iunie 2011 14:00:15
Problema Castel Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.23 kb
#include <cstdio>
#include <vector>
#include <cstring>
using namespace std;

#define MAXN 155

int main(){

  freopen("castel.in", "r", stdin);
  freopen("castel.out", "w", stdout);

  int N, M, S, i, j, l, r, x, y, aux, cnt;
  int C[MAXN][MAXN], K[MAXN*MAXN], Qx[MAXN*MAXN], Qy[MAXN*MAXN], use[MAXN][MAXN];
  vector<int> Ux[MAXN*MAXN], Uy[MAXN*MAXN]; 
  vector<int>::iterator ii, jj;
  int dx[]={1, 0, -1, 0}, dy[]={0, 1, 0, -1};

  memset(C, 0, sizeof(C));

  scanf("%d%d%d", &N, &M, &S);
  for(i=1; i<=N; i++)
    for(j=1; j<=M; j++)
      scanf("%d", &C[i][j]);

  memset(K, 0, sizeof(0));

  memset(use, 0, sizeof(use));
  l=r=1; Qx[1]=S/M+1; Qy[1]=S%M;
  if(!Qy[1]){
    Qy[1]=M;
    Qx[1]--;
  }

  use[Qx[1]][Qy[1]]=1;

  cnt=1;
  while(l<=r){

    K[aux=((Qx[l]-1)*M+Qy[l])]=1;

    for(ii=Ux[aux].begin(), jj=Uy[aux].begin(); ii!=Ux[aux].end(); ii++, jj++){
      cnt++;
      Qx[++r]=*ii;
      Qy[r]=*jj;
    }

    for(i=0; i<4; i++){
      x=Qx[l]+dx[i];
      y=Qy[l]+dy[i];
      if(!use[x][y]){
	if(K[C[x][y]]){
	  cnt++;
	  use[x][y]=1;
	  Qx[++r]=x;
	  Qy[r]=y;
	}
	else if(C[x][y]){
	  Ux[C[x][y]].push_back(x);
	  Uy[C[x][y]].push_back(y);
	  use[x][y]=1;
	}
      }
    }
    
    l++;
    
  }

  printf("%d\n", cnt);

  return 0;

}