Cod sursa(job #262739)

Utilizator FlorianFlorian Marcu Florian Data 19 februarie 2009 16:49:39
Problema Castel Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.45 kb
#include<stdio.h>
#define Nmax 153
FILE*f=freopen("castel.in","r",stdin);
FILE*g=freopen("castel.out","w",stdout);
struct Key
 {
  int room;
  Key *next;
 };
Key *G[Nmax*Nmax]; // G[i] = lista camerelor care sunt deschide de cheia i
short viz[Nmax*Nmax];// viz[i] - camera a fost vizitata
int a[Nmax*Nmax];//camera care trebuie deschisa pt a deschide camera i
int n,m,k;
void insert(int x, int y) // daca deschid x pot deschide si y
 {
  Key *q;
  q=new Key;
  q->next = G[x];
  q->room = y;
  G[x] = q;
 }
void read()
 {
  scanf("%d%d%d",&n,&m,&k);
  int i,j,x;
  for(i=1;i<=n;++i)
   for(j=1;j<=m;++j)
    {
     scanf("%d",&x);
     // deschid camera [(i-1)*m + j] cu cheia x
     a[(i-1)*m+j] = x;
    }
  }
int c[Nmax*Nmax],p=0,u=0,x;
void vec(int y)
 {
  if(viz[y]);
  else {if(viz[a[y]])
   {
    viz[y]=1;
    c[++u]=y;
   }
  else insert(a[y],y);     }
 }

void solve()
 {
  Key *q;
  c[u] = k;
  viz[k]=1;
  while(p<=u)
   {
    x=c[p++];
    for(q=G[x];q;q=q->next)
     {
     if(!viz[q->room])
      {
      viz[q->room] = 1;
      c[++u] = q->room;
      }
     }
    //vecinii orizontali
    if(x%m==1) vec(x+1);
    else if(x%m==0) vec(x-1);
    else { vec(x+1), vec(x-1); }

    // vecinii verticali
    if(1<=x && x<=m) vec(x+m);
    else if(x >= (n-1)*m+1) vec(x-m);
    else { vec(x-m); vec(x+m); }
   }
  printf("%d\n",u+1);
 }
int main()
 {
  read();
  solve();
  return 0;
 }