Submission #498316

#	Time	Username	Problem	Language	Result	Execution time	Memory
498316		chenwz	Mecho (IOI09_mecho)	C++11	100 / 100	179 ms	21572 KiB

mecho

// IOI2009 - Mecho
#include <bits/stdc++.h>
using namespace std;
const int NN = 2000 + 4, DX[4] = {1, -1, 0, 0}, DY[4] = {0, 0, 1, -1};
#define _for(i, a, b) for (int i = (a); i < (int)(b); ++i)
string G[NN];
int N, S, D[NN][NN];
bool Vis[NN][NN];
struct Point {
  int x, y;
};
bool valid(int x, int y) {
  return 0 <= x && x < N && 0 <= y && y < N;
  // nx < 0 || nx >= N || ny < 0 || ny >= N
}
bool check(const Point& st, const Point& ed,
           int delay) {  // 小熊delay再出发够不?
  if (delay * S >= D[st.x][st.y]) return false;
  queue<pair<int, Point> > Q;  // {当前时间，当前位置}
  memset(Vis, 0, sizeof(Vis)), Q.push({delay * S, st}), Vis[st.x][st.y] = true;
  while (!Q.empty()) {
    auto p = Q.front();
    Q.pop();
    int d = p.first, x = p.second.x, y = p.second.y;
    // if (G[x][y] == 'D')
    if (x == ed.x && y == ed.y) return true;  // 到家
    _for(i, 0, 4) {
      int nx = x + DX[i], ny = y + DY[i];
      if (valid(nx, ny) && G[nx][ny] != 'T' && d + 1 < D[nx][ny] &&
          !Vis[nx][ny])
        // if (nx < 0 || nx >= N || ny < 0 || ny >= N || G[nx][ny] == 'T' ||
        //     (d + 1) >= D[nx][ny] || Vis[nx][ny])
        //   continue;
        Q.push({d + 1, {nx, ny}}), Vis[nx][ny] = true;
    }
  }
  return false;
}
int main() {
  ios::sync_with_stdio(false), cin.tie(0);
  cin >> N >> S;
  queue<Point> Q;
  Point st, ed;
  memset(D, -1, sizeof(D));
  _for(i, 0, N) {
    cin >> G[i];
    _for(j, 0, N) {
      char& c = G[i][j];
      if (c == 'H') Q.push({i, j}), D[i][j] = 0;
      if (c == 'M') st = {i, j}, c = 'G';  // 初始小熊位置也改成草
      if (c == 'D') ed = {i, j};           // 家的位置
    }
  }
  while (!Q.empty()) {  // BFS计算每个点到最近的蜜蜂的距离
    Point p = Q.front();
    Q.pop();
    _for(i, 0, 4) {
      int nx = p.x + DX[i], ny = p.y + DY[i], &nd = D[nx][ny];
      if (valid(nx, ny) && G[nx][ny] == 'G' && nd == -1)
        // if (!valid(nx, ny) || G[nx][ny] != 'G' || D[nx][ny] != -1) continue;
        nd = D[p.x][p.y] + S, Q.push({nx, ny});
    }
  }
  D[ed.x][ed.y] = N * N * S;
  int L = -1, R = 2 * N * N;
  while (L + 1 < R) {
    int mid = (L + R) / 2;  // 推迟mid出发够不够
    (check(st, ed, mid) ? L : R) = mid;
  }
  cout << L << endl;
  return 0;
}
// 2021-12-20 Mecho (IOI09_mecho) C++11 100/100 180 ms 21600 KB

• Subtask 1: 100 / 100