Cod sursa(job #2144632)

Utilizator DruffbaumPopescu Vlad Druffbaum Data 26 februarie 2018 20:45:05
Problema Castel Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.25 kb
#include <cstdio>
#include <vector>
#include <queue>

#define MAXN 150
#define NUM_DIR 4

const int delta[NUM_DIR][2] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};

std::vector <int> v[MAXN * MAXN];
bool vis[MAXN][MAXN], r[MAXN * MAXN];
int a[MAXN][MAXN];
std::queue <int> q;

int main() {
  FILE *fin, *fout;
  int n, m, k, cr, x, y, ans;
  fin = fopen("castel.in", "r");
  fscanf(fin, "%d%d%d", &n, &m, &k);
  for (int i = 0; i < n; ++i) {
    for (int j = 0; j < m; ++j) {
      fscanf(fin, "%d", &a[i][j]);
      --a[i][j];
    }
  }
  fclose(fin);
  ans = 0;
  q.push(--k);
  vis[k / m][k % m] = 1;
  while (!q.empty()) {
    ++ans;
    cr = q.front();
    r[cr] = 1;
    q.pop();
    for (auto i: v[cr]) {
      if (!vis[i / m][i % m]) {
        vis[i / m][i % m] = 1;
        q.push(i);
      }
    }
    for (int i = 0; i < NUM_DIR; ++i) {
      x = cr / m + delta[i][0];
      y = cr % m + delta[i][1];
      if (0 <= x && 0 <= y && x < n && y < m && !vis[x][y]) {
        if (r[a[x][y]]) {
          q.push(x * m + y);
          vis[x][y] = 1;
        } else {
          v[a[x][y]].push_back(x * m + y);
        }
      }
    }
  }
  fout = fopen("castel.out", "w");
  fprintf(fout, "%d\n", ans);
  fclose(fout);
  return 0;
}