Submission #1082845

#	Time	Username	Problem	Language	Result	Execution time	Memory
1082845		v_matei	Mecho (IOI09_mecho)	C++17	20 / 100	1096 ms	65536 KiB

mecho

#include <bits/stdc++.h>
#include <functional>
#include <queue>
#include <vector>

#define ll long long
#define ull unsigned long long
#define pii std::pair<int, int>

#define IO (std::string) ""
std::ifstream fin(IO + ".in");
std::ofstream fout(IO + ".out");

#define NMAX 1000
#define INF INT_MAX

int n, s;
char map[NMAX][NMAX];
pii start, finish;
std::vector<pii> hives;
std::map<pii, int> d1, d2, d;

int di[]{1, -1, 0, 0}, dj[]{0, 0, 1, -1};

void citire() {
  std::cin >> n >> s;
  for (int i = 0; i < n; i++)
    for (int j = 0; j < n; j++) {
      std::cin >> map[i][j];
      if (map[i][j] == 'M')
        start = {i, j};
      if (map[i][j] == 'D')
        finish = {i, j};
      if (map[i][j] == 'H')
        hives.push_back({i, j});
    }
}

bool in(pii coord) {
  int i = coord.first, j = coord.second;
  return i >= 0 && i < n && j >= 0 && j < n;
}

void bfs(std::queue<pii> &q, std::map<pii, int> &d,
         std::function<bool(pii coords)> check) {
  while (!q.empty()) {
    pii u = q.front();
    int i = u.first;
    int j = u.second;
    q.pop();

    for (int k = 0; k < 4; k++) {
      int ni = i + di[k];
      int nj = j + dj[k];
      if (check({ni, nj}) && d[{ni, nj}] > d[{i, j}] + 1) {
        d[{ni, nj}] = d[{i, j}] + 1;
        q.push({ni, nj});
      }
    }
  }
}

std::map<pii, bool> vis;
int ans = -1;

void dfs(pii nod, int k, int curr_min) {
  vis[nod] = 1;
  if (k % s == 0)
    curr_min = std::min(curr_min, abs(k / s + 1 - d2[nod]));

  if (nod == finish) {
    ans = std::max(ans, curr_min);
    // for (int i = 0; i <= k; i++)
    // std::cout << "{" << a[i].first << "," << a[i].second << "}" << ' ';
    // std::cout << '\n';
  }
  for (int i = 0; i < 4; i++) {
    pii nou = {nod.first + di[i], nod.second + dj[i]};
    if (!vis[nou] && d2[nou] * s > k + 1 && in(nou) &&
        map[nou.first][nou.second] != 'T') {
      dfs(nou, k + 1, curr_min);
    }
  }
  vis[nod] = 0;
}

int main() {
  std::cin.tie(0)->std::ios::sync_with_stdio(0);
  citire();

  std::queue<pii> q;

  for (int i = 0; i < n; i++)
    for (int j = 0; j < n; j++) {
      d[{i, j}] = d1[{i, j}] = d2[{i, j}] = INF;
    }

  for (pii it : hives) {
    q.push(it);
    d2[it] = 0;
  }

  bfs(q, d2, [&](pii coords) {
    return in(coords) && map[coords.first][coords.second] != 'D' &&
           map[coords.first][coords.second] != 'T';
  });

  dfs(start, 0, INF);

  std::cout << ans << '\n';
  /*for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
      if (d2[{i, j}] != INF)
        std::cout << d2[{i, j}] << ' ';
      else
        std::cout << "oo ";
    }
    std::cout << '\n';
  }*/
  return 0;
}

• Subtask 1: 20 / 100