Cod sursa(job #199029)

Utilizator Pepelea_FlaviuFlaviu Pepelea Pepelea_Flaviu Data 16 iulie 2008 18:22:09
Problema Castel Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.01 kb
# include <stdio.h>
# include <vector>

using namespace std;

# define FIN "castel.in"
# define FOUT "castel.out"
# define MAXN 23000
# define MAXM 152

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

int a[MAXM][MAXM];
unsigned char s[MAXN];
int q[MAXN];
vector <int> key[MAXN];
int N,M,k,ct,i,j,f,l,aux,x,tt=0;

    int main()
    {
        freopen(FIN,"r",stdin);
        freopen(FOUT,"w",stdout);
        
        scanf("%d%d%d",&N,&M,&k);
        for (i = 1; i <= N; ++i)
          for (j = 1; j <= M; ++j)
            scanf("%d",&a[i][j]);
            
        int xo,yo;    
        f = 0;
        l = 1;
        q[f] = k;
        s[k] = 1;
        ct = 1;
        while (f<l)
          {
              x = q[f++];
              aux = key[x].size();
              for (i = 0; i < aux; ++i)
                if (s[key[x][i]]==0) 
                  {
                     q[l++] = key[x][i];
                     s[key[x][i]] = 1;
                     ct++;
                  }
              if (x % M == 0)
                {
                    xo = x/M;
                    yo = M;
                }
              else
                {
                    xo = x/M+1;
                    yo = x%M;
                }
              for (i = 0; i < 4; ++i)
                if (a[xo+dx[i]][yo+dy[i]]!=0)
                  {
                      if (yo+dy[i]==M) aux=M*(xo+dx[i]);
                      else aux=M*(xo+dx[i]-1)+yo+dy[i];
                      if (s[aux] == 0)
                        {
                            if (s[a[xo+dx[i]][yo+dy[i]]]==1)
                              {
                                  s[aux] = 1;
                                  q[l++] = aux;
                                  ct++;
                              }
                            else key[a[xo+dx[i]][yo+dy[i]]].push_back(aux);
                        }
                  }
          }
          
        printf("%d",ct);
          
        return 0;
    }