제출 #1112344

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1112344		greenbinjack	Mecho (IOI09_mecho)	C++17	38 / 100	233 ms	9628 KiB

mecho

#include <bits/stdc++.h>
using namespace std;

#define all(V) V.begin(), V.end()
#define x first
#define y second

using LL = long long;

const int N = 808;

int dx[4] = {+1, -1, 0, 0};
int dy[4] = {0, 0, +1, -1};

char grid[N][N];  
int n, k, bees[N][N];
pair <int, int> start, finish;

bool valid (int i, int j) {
  return (i > 0 and i <= n and j > 0 and j <= n);
}

bool check (int Time) {
  queue < pair <int, int> > q;
  q.push (start);
  vector < vector < pair <int, int> > > dist (n + 1, vector < pair <int, int> > (n + 1, {INT_MAX, 0}));
  dist[start.x][start.y] = {Time, 0};
  while (!q.empty ()) {
    auto [X, Y] = q.front ();
    q.pop ();
    for (int i = 0; i < 4; i++) {
      int nwX = X + dx[i], nwY = Y + dy[i];
      if (valid (nwX, nwY) and (grid[nwX][nwY] == 'G' or grid[nwX][nwY] == 'D')) {
        if (dist[X][Y].x + (dist[X][Y].y == k) < dist[nwX][nwY].x and dist[X][Y].x + (dist[X][Y].y == k) < bees[nwX][nwY]) {
          if (dist[X][Y].y == k) dist[nwX][nwY] = {dist[X][Y].x + 1, 1};
          else dist[nwX][nwY] = {dist[X][Y].x, dist[X][Y].y + 1};
          q.push ({nwX, nwY});
        }
      }
    }
  }
  return dist[finish.x][finish.y].x != INT_MAX;
}

int main() {
  cin.tie (nullptr) -> ios_base :: sync_with_stdio (false);

  cin >> n >> k;
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= n; j++) {
      cin >> grid[i][j];
      if (grid[i][j] == 'M') start = {i, j};
      if (grid[i][j] == 'D') finish = {i, j};
    }
  }
  
  queue < pair <int, int> > q;
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= n; j++) {
      if (grid[i][j] == 'H') {
        q.push ({i, j});
        bees[i][j] = 0;
      } else {
        bees[i][j] = INT_MAX;
      }
    }
  }

  while (!q.empty ()) {
    auto [X, Y] = q.front ();
    q.pop ();
    for (int i = 0; i < 4; i++) {
      int nwX = X + dx[i], nwY = Y + dy[i];
      if (!valid (nwX, nwY)) continue;
      if (valid (nwX, nwY) and (grid[nwX][nwY] == 'G' or grid[nwX][nwY] == 'M') and bees[X][Y] + 1 < bees[nwX][nwY]) {
        bees[nwX][nwY] = bees[X][Y] + 1;
        q.push ({nwX, nwY});
      }
    }
  }

  int left = 0, right = n * n;
  while (left < right) {
    int mid = (left + right + 1) >> 1;
    if (check (mid)) left = mid;  
    else right = mid - 1;
  }

  if (!check (left)) left--;

  cout << left << '\n';

  return 0;
}

• Subtask 1: 38 / 100