Cod sursa(job #54164)

Utilizator pauldbPaul-Dan Baltescu pauldb Data 24 aprilie 2007 13:38:59
Problema Castel Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.59 kb
#include <stdio.h>
#include <vector>

using namespace std;

#define maxn 160
#define maxx 45010
#define maxl 4
#define pb push_back

int n,m,l,k,sol;
char used[maxn][maxn],own[maxn];
int a[maxn][maxn];
int s[maxx];
int dirx[maxl]={-1,1,0,0};
int diry[maxl]={0,0,-1,1};
vector <int> key[maxn];

void dcv(int a,int &x,int &y)
{
     if (a%m==0) 
     {
         y=m;
         x=a/m;
     }
     else { 
              y=a%m;
              x=a/m+1;
          }
}

int cv(int x,int y)
{
    return (x-1)*m+y;
}

int main()
{
    freopen("castel.in","r",stdin);
    freopen("castel.out","w",stdout);
    
    scanf("%d %d %d",&n,&m,&k);
    
    int i,j,x,y,cx,cy,aux,g;
    
    for (i=1;i<=n;i++) 
      for (j=1;j<=m;j++) scanf("%d ",&a[i][j]);
      
    l=1;
    s[l]=k;
    dcv(k,x,y);
    used[x][y]=1;
    own[k]=1;
    
    for (i=1;i<=l;i++)
    {
        dcv(s[i],x,y);
        
        if ((own[a[x][y]]) || (i==1))
        {
            own[s[i]]=1;
            g=key[s[i]].size();
            
            for (j=0;j<g;j++) s[++l]=key[s[i]][j];
            
            for (j=0;j<maxl;j++)
            {
                cx=x+dirx[j];
                cy=y+diry[j];
                
                if ((cx>0) && (cy>0) && (cx<=n) && (cy<=m) && (!used[cx][cy]))
                {
                    s[++l]=cv(cx,cy);  
                    used[cx][cy]=1;
                }
            }
        }
        else key[a[x][y]].pb(s[i]);
    }
    
    for (i=1;i<=n*m;i++) sol+=own[i];
    
    printf("%d\n",sol);
    
    return 0;
}