Cod sursa(job #2191422)

Utilizator vladisimovlad coneschi vladisimo Data 2 aprilie 2018 19:58:51
Problema Castel Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.28 kb
#include <cstdio>
#include <vector>
#include <queue>

const int dl[4] = {-1, 0, 1, 0};
const int dc[4] = {0, 1, 0, -1};

int main() {
  freopen("castel.in", "r", stdin);
  freopen("castel.out", "w", stdout);
  int n, m, k;
  scanf("%d%d%d", &n, &m, &k);
  int key[2 + n * m];
  bool is[2 + n * m];
  std::vector <int> open[2 + n * m];
  for (int i = 1; i <= n; i++)
    for (int j = 1; j <= m; j++) {
      scanf("%d", &key[m * (i - 1) + j]);
      open[key[m * (i - 1) + j]].push_back(m * (i - 1) + j);
      is[m * (i - 1) + j] = false;
    }
  std::queue <int> q;
  q.push(k);
  while (!q.empty()) {
    int w = q.front();
    for (int i : open[w])
      if (!is[i]) {
        is[i] = true;
        q.push(i);
      }
    int i = (w - 1) / m + 1, j = (w - 1) % m + 1;
    for (int h = 0; h <= 3; h++) {
      int iN = i + dl[h];
      int jN = j + dc[h];
      if (iN > 0 && jN > 0 && iN < n + 1 && jN < m + 1) {
        int wN = m * (iN - 1) + jN;
        if (!is[wN]) {
          if (is[key[wN]]) {
            is[wN] = true;
            q.push(wN);
          } else
            open[key[wN]].push_back(wN);
        }
      }
    }
    q.pop();
  }
  int sol = 0;
  for (int i = 1; i <= n * m; i++)
    sol += is[i];
  printf("%d", sol);
  return 0;
}