제출 #320376

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
320376		AlexLuchianov	Mecho (IOI09_mecho)	C++14	100 / 100	271 ms	7140 KiB

mecho

#include <iostream>
#include <vector>
#include <cassert>
#include <queue>
#include <algorithm>

using ll = long long;
#define MIN(a, b) (((a) < (b)) ? (a) : (b))
#define MAX(a, b) (((a) < (b)) ? (b) : (a))

int const nmax = 800;
int const iplus[4] = {0, 0, 1, -1};
int const jplus[4] = {1, -1, 0, 0};

char v[1 + nmax][1 + nmax];
int n, k;

bool valid(int x, int y) {
  return 1 <= x && x <= n && 1 <= y && y <= n;
}
int bee[1 + nmax][1 + nmax];

void add_bees() {
  std::queue<std::pair<int,int>> q;
  for(int i = 1;i <= n; i++)
    for(int j = 1;j <= n; j++)
      bee[i][j] = -1;
  for(int i = 1;i <= n; i++)
    for(int j = 1;j <= n; j++)
      if(v[i][j] == 'H') {
        bee[i][j] = 0;
        q.push({i, j});
      }
  
  while(0 < q.size()) {
    int x = q.front().first;
    int y = q.front().second;
    q.pop();

    for(int h = 0; h < 4; h++) {
      int newx = x + iplus[h];
      int newy = y + jplus[h];
      if(valid(newx, newy) == 1 && (v[newx][newy] == 'G' || v[newx][newy] == 'M'))
        if(bee[newx][newy] == -1) {
          bee[newx][newy] = bee[x][y] + 1;
          q.push({newx, newy});
        }
    }
  }
  /*
  std::cout << "bees\n";
  for(int i = 1;i <= n; i++) {
    for(int j = 1; j <= n; j++)
      std::cout << bee[i][j] << " ";
    std::cout << '\n';
  }
  */
}

int dp[1 + nmax][1 + nmax];

bool can_reach(int _sleep) {
  for(int i = 1;i <= n; i++)
    for(int j = 1;j <= n; j++)
      dp[i][j] = -1;
  std::queue<std::pair<int,int>> q;

  for(int i = 1;i <= n; i++) 
    for(int j = 1;j <= n; j++)
      if(v[i][j] == 'M') {
        if(_sleep < bee[i][j]) {
          q.push({i, j});
          dp[i][j] = _sleep * k;
        }
      }
  while(0 < q.size()) {
    int x = q.front().first;
    int y = q.front().second;
    if(v[x][y] == 'D')
      return true;
    q.pop();
    for(int h = 0;h < 4; h++) {
      int newx = x + iplus[h];
      int newy = y + jplus[h];
      if(valid(newx, newy) && (v[newx][newy] == 'G' || v[newx][newy] == 'D'))
        if(dp[newx][newy] == -1 && (v[newx][newy] == 'D' || dp[x][y] + 1 < bee[newx][newy] * k || bee[newx][newy] == -1)) {
          dp[newx][newy] = dp[x][y] + 1;
          q.push({newx, newy});
        }
    }
  }
  return false;
}

int main() {
  std::cin >> n >> k;
  for(int i = 1;i <= n; i++)
    for(int j = 1; j <= n; j++)
      std::cin >> v[i][j];
  add_bees();
  if(can_reach(0) == false)
    std::cout << -1;
  else {
    int x = 0;
    for(int jump = (1 << 20); 0 < jump; jump /= 2)
      if(can_reach(x + jump) == true)
        x += jump;
    std::cout << x;
  }

  return 0;
}

• Subtask 1: 100 / 100