Cod sursa(job #2809327)

Utilizator PetyAlexandru Peticaru Pety Data 26 noiembrie 2021 17:57:29
Problema Castel Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.26 kb
#include <bits/stdc++.h>
#define ll long long
#define ld long double

using namespace std;

const int N = 150;

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


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


int key[N * N + 2], v[N + 2][N + 2], n, m, k;
bool viz[N + 2][N + 2];
vector<pair<int, int>>points[N * N + 2];
queue<pair<int, int> > q;

int bfs (int k) {
  key[k] = 1;
  q.push({(k - 1) / m + 1, (k - 1) % m + 1});
  int cnt = 0;
  while (q.size()) {
    auto p = q.front();
    cnt++;
    q.pop();
    for (int k = 0; k < 4; k++) {
      int x = p.first + dl[k];
      int y = p.second + dc[k];
      if (x < 1 || x > n || y < 1 || y > m || viz[x][y])
        continue;
      if (key[v[x][y]]) {
        q.push({x, y});
        for (auto it : points[(x - 1) * m + y]) {
          q.push(it);
          viz[it.first][it.second] = 1;
        }
        points[(x - 1) * m + y].clear();
        key[(x - 1) * m + y] = 1;
        viz[x][y] = 1;
      } 
      else {
        points[key[v[x][y]]].push_back({x, y});
      }
    }
  }
  return cnt;
}

int main()
{
  //ios_base::sync_with_stdio(false);
  //cin.tie(0); cout.tie(0);
  fin >> n >> m >> k;
  for (int i = 1; i <= n; i++)
    for (int j = 1; j <= m; j++)
      fin >> v[i][j];
  fout << bfs(k);
  return 0;
}