Cod sursa(job #861825)

Utilizator andrici_cezarAndrici Cezar andrici_cezar Data 21 ianuarie 2013 22:18:16
Problema Castel Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.01 kb
#include <cstdio>
#include <queue>
#include <utility>
#include <vector>

using namespace std;

vector < queue < pair<int, int> > > v(22501);
queue < pair<int, int> > q;
int N, M, K, chei[22501], a[151][151], viz[151][151];

inline int indJ(int x) {
  return ((x % M == 0)?M:(x%M));
}

inline int indI(int x) {
  return (x-indJ(x))/M + 1;
}

inline bool daca_e_in_matrice( pair<int, int> x) {
  if (x.first < 1) return false;
  if (x.second < 1) return false;
  if (x.first > N) return false;
  if (x.second > M) return false;
  return true;
}

inline bool daca_exista_cheie( int x) {
  return (chei[x]==1);
}

void adauga_cheie( pair <int, int> z) {
  int x = (z.first-1)*M + z.second;
  if ( chei[x] == 1) return;
  
  chei[x] = 1;

  for (; !v[x].empty(); v[x].pop()) {
    q.push( v[x].front() );
    viz[v[x].front().first][v[x].front().second] = 1;
  }
}

void incearca( pair <int, int> x) {

  int d1[4] = {0, 1, 0, -1};
  int d2[4] = {1, 0, -1, 0};

  for (int i = 0; i < 4; ++i) {
    pair <int, int> aux;
    aux = x;
    aux.first += d1[i];
    aux.second += d2[i];

    if (!daca_e_in_matrice(aux)) continue;
    if (viz[aux.first][aux.second] == 1) continue;

    if (daca_exista_cheie( a[aux.first][aux.second] )) {
      viz[aux.first][aux.second] = 1;
      adauga_cheie( aux );
      q.push(aux);
    } else {
      v[a[aux.first][aux.second]].push(aux);
    }
  }

}

int main() {
  freopen("castel.in", "r", stdin);
  freopen("castel.out", "w", stdout);

    scanf("%d %d %d", &N, &M, &K);

    for (int i = 1; i <= N; ++i) {
      for (int j = 1; j <= M; ++j) {
        scanf("%d", &a[i][j]);
      }
    }

    adauga_cheie( make_pair(indI(K), indJ(K)) );
    viz[indI(K)][indJ(K)] = 1;
    q.push( make_pair(indI(K), indJ(K)) );

    for (; !q.empty(); q.pop() ) {
    //  printf( "%d\n", (q.front().first-1)*M+q.front().second );
      incearca( q.front() );
    }

    int nr = 0;
    for (int i = 1; i <= N; ++i) {
      for (int j = 1; j <= M; ++j) {
        nr += viz[i][j];
      }
    }

    printf("%d\n", nr);

  return 0;
}