Cod sursa(job #1087566)

Utilizator httpsLup Vasile https Data 19 ianuarie 2014 16:25:55
Problema Castel Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.91 kb
#include <iostream>
#include <fstream>
#include <queue>
using namespace std;

ifstream f("castel.in");
ofstream g("castel.out");

#define nmax 151
#define cout g
int n,m,i,j,k,nr,last_nr;
int a[nmax][nmax],stare[nmax][nmax],key[nmax*nmax];
int to_x(int k)
{
  return (k-1)/m+1;
}
int to_y(int k)
{
  return (k-1)%m+1;
}
int to_key(int i,int j)
{
  return (i-1)*m+j;
}
int deplx(int x,int i)
{
  if (i==1) return x-1;
  else if (i==2) return x;
  else if (i==3) return x+1;
  else return x;
}
int deply(int y,int i)
{
  if (i==1) return y;
  else if (i==2) return y+1;
  else if (i==3) return y;
  else return y-1;
}
void afisare(int v[][nmax])
{int i,j;
    for(i=1;i<=n;i++)
  {
      for(j=1;j<=m;j++) cout<<v[i][j]<<' ';
      cout<<"\n";
  }
  cout<<"*************************\n";
}
void parcurge(int x,int y)
{
  int nx,ny;
  queue <int> q;
  q.push(to_key(x,y));
  stare[x][y]=1;
  nr++;
  key[q.front()]=1;
  while (!q.empty())
    {
      x=to_x(q.front());
      y=to_y(q.front());
      q.pop();
      //afisare(stare);
      for(int i=1; i<=4; i++)
        {
          nx=deplx(x,i);
          ny=deply(y,i);
          if (a[nx][ny]>0 && stare[nx][ny]!=1)
            if(key[a[nx][ny]])
              {
                nr++;
                stare[nx][ny]=1;
                key[to_key(nx,ny)]=1;
                q.push(to_key(nx,ny));
              }
            else stare[nx][ny]=2;
        }

    }
}
int main()
{
  f>>n>>m>>k;
  for(i=1; i<=n; i++)
    for(j=1; j<=m; j++) f>>a[i][j];

  key[k]=1;
  parcurge(to_x(k),to_y(k));
//afisare(stare);
  bool ok=true;
  while (ok)
  {
      last_nr=nr;
      for(i=1;i<=n;i++)
      for (j=1;j<=m;j++)
      if (stare[i][j]==2 && key[a[i][j]])
            parcurge(i,j);
    //  afisare(stare);
      if (nr==last_nr) ok=false;
  }
  cout<<nr;
  //cout<<'\n';
//afisare(stare);
  return 0;
}