Cod sursa(job #658737)

Utilizator vendettaSalajan Razvan vendetta Data 9 ianuarie 2012 14:14:21
Problema Castel Scor 60
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.81 kb
#include <fstream>
#include <queue>
#define nmax 151

using namespace std;

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

int n, m, A, viz[nmax*nmax];
queue<pair<int,int> > v[nmax*nmax];
queue<pair<int,int> > Q;
int a[nmax][nmax], b[nmax][nmax];
int sol;

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

void citeste(){

   f>>n>>m>>A;

   int k = 0;

   for(int i=1; i<=n; ++i){
      for(int j=1; j<=m; ++j){
         ++k;
         f>>a[i][j];
         b[i][j] = k;
         if ( k == A ) Q.push(make_pair(i,j)), viz[k] = 1;
      }
   }

}

int check(int x, int y){

   if ( x > 0 && y > 0 && x <= n && y <= m) return 1;
   return 0;

}

void rezolva(){

   for(; Q.size(); ){
      int x = (Q.front()).first;
      int y = (Q.front()).second;
      Q.pop();
      int N = b[x][y];
      if (v[N].size())
         //for(int i=0; i < v[N].size(); ++i){
           for(; v[N].size(); ){
            int xx = (v[N].front()).first;
            int yy = (v[N].front()).second;
            v[N].pop();
            Q.push(make_pair(xx,yy));
            viz[b[xx][yy]] = 1;
         }

      for(int k=0; k<4; ++k){
         int ii = x + dx[k];
         int jj = y + dy[k];
         int nr = b[ii][jj];
         if (check(ii,jj) && viz[ nr ] == 0){
            //viz[nr] = 1;
            if (viz[a[ii][jj]] == 1){
               viz[nr] = 1;
               Q.push(make_pair(ii,jj));
               //++sol;
            }else v[ a[ii][jj] ].push(make_pair(ii,jj));
         }
      }
   }

}


void scrie(){

   for(int i=1; i<=n; ++i)
      for(int j=1; j<=m; ++j)
         sol += viz[b[i][j]];

   g<<sol<<"\n";

}

int main(){

   citeste();
   rezolva();
   //g<<viz[1]<<"\n";
   scrie();

   f.close();
   g.close();

   return 0;

}