Cod sursa(job #2746047)

Utilizator bogdanvladmihaiBogdan Vlad-Mihai bogdanvladmihai Data 27 aprilie 2021 13:45:52
Problema Castel Scor 30
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.63 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[sigma];

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) {
  return (a - 1) * 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;
  code[1] = make_pair(1, 1);
  for (int i = 2; i <= n * m; i++) {
    code[i] = code[i - 1];
    code[i].second++;
    if (code[i].second == m + 1) {
      code[i].second = 1;
      code[i].first++;
    }
  }
  while ((int)q.size() > 0) {
    ans++;
    int u = q.front();
    q.pop();
    access[u] = true;
    int x = code[u].first, y = code[u].second;
    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);
      if (!inside(nx, ny) || used[key] == true) {
        continue;
      }
      if (access[val] == true) {
        q.push(key);
        used[key] = true;
      } else {
        g[val].push_back(key);
      }
    }
    for (int v : g[u]) {
      if (!used[v]) {
        used[v] = true;
        q.push(v);
      }
    }
  }
  out << ans << "\n";
  return 0;
}