Cod sursa(job #2745778)

Utilizator bogdanvladmihaiBogdan Vlad-Mihai bogdanvladmihai Data 26 aprilie 2021 23:41:42
Problema Castel Scor 30
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.72 kb
#include <bits/stdc++.h>
 
using namespace std;

#define deb(x) << "[" << #x << " = " << x << "] "
 
using ll = long long;

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

const int ox[] = {0, 1, 0, -1};
const int oy[] = {1, 0, -1, 0};
const int maxN = (int)2e2 + 5;
const int sigma = maxN * maxN;

int n, m, k;

int mat[maxN][maxN];

bool used[maxN * maxN], access[maxN];

vector<int> g[sigma];

pair<int, int> code(int val) {
  pair<int, int> ans;
  ans.second = val % m;
  ans.first = val / m;
  if (val % m == 0) {
    ans.second = m;
  } else {
    ans.first++;
  }
  return ans;
}

bool inside(int x, int y) {
  if (x >= 1 && y >= 1 && x <= n && y <= m) {
    return true;
  }
  return false;
}

int convert(int a, int b) {
  a--;
  return a * m + b;
}

int main() {
  in >> n >> m >> k;
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= m; j++) {
      in >> mat[i][j];
    } 
  }
  queue<int> q;
  q.push(k);
  used[k] = true;
  int ans = 0;
  while ((int)q.size() > 0) {
    ans++;
    int u = q.front();
    q.pop();
    access[u] = true;
    for (int v : g[u]) {
      if (!used[v]) {
        used[v] = true;
        q.push(v);
      }
    }
    int x = code(u).first, y = code(u).second;
  //  cerr deb(x) << " " deb(y) << " " deb(mat[x][y]) << " " deb(u) << "\n";
    for (int i = 0; i < 4; i++) {
      int nx = x + ox[i];
      int ny = y + oy[i];
      int val = mat[nx][ny];
      int key = convert(nx, ny);
    //  cerr deb(key) << " " deb(nx) << " " deb(ny) << "\n";
      if (!inside(nx, ny) || used[key] == true) {
        continue;
      }
      if (access[val] == true) {
        q.push(key);
        used[key] = true;
      } else {
        g[val].push_back(key);
      }
    }
  }
  out << ans << "\n";
  return 0;
}