제출 #1201229

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1201229		SonicML	Mecho (IOI09_mecho)	C++20	100 / 100	261 ms	2584 KiB

mecho

#include <iostream>
#include <queue>

using namespace std;

int const NMAX = 800;
char mat[1 + NMAX][1 + NMAX];
bool isBee[1 + NMAX][1 + NMAX];
bool isBear[1 + NMAX][1 + NMAX];

struct Point{
  int x;
  int y;
};

int dirX[4] = {-1, 0, 1, 0};
int dirY[4] = {0, -1, 0, 1};

bool isValid(Point to, int n) {
  return (1 <= to.x && to.x <= n && 1 <= to.y && to.y <= n && mat[to.x][to.y] != 'T' && isBee[to.x][to.y] == false); 
}

bool canBear(int n, int step, int delay) {
  Point fin;
  queue <Point> bear, bee;
  for(int i = 1;i <= n;i++) {
    for(int j = 1;j <= n;j++) {
      isBee[i][j] = isBear[i][j] = false;
      if(mat[i][j] == 'D') {
	fin = {i, j};
      }
      if(mat[i][j] == 'H') {
	isBee[i][j] = true;
	bee.push({i, j});
      }
      if(mat[i][j] == 'M') {
	isBear[i][j] = true;
	bear.push({i, j});
      }
    }
  } 
  for(int s = 1;s <= delay;s++) {
    int waveSize = bee.size();
    for(int i = 1;i <= waveSize;i++) {
      Point from = bee.front();
      bee.pop();
      for(int dir = 0;dir < 4;dir++) {
	Point to = {from.x + dirX[dir], from.y + dirY[dir]};
	if(isValid(to, n) && mat[to.x][to.y] != 'D') {
          bee.push(to);
	  isBee[to.x][to.y] = true;
	}
      }
    }
  }
  while(!bear.empty()) {
    for(int s = 1;s <= step;s++) { 
      int waveSize = bear.size();
      for(int i = 1;i <= waveSize;i++) {
        Point from = bear.front();
	bear.pop();
	if(!isBee[from.x][from.y]) {
  	  for(int dir = 0;dir < 4;dir++) {
            Point to = {from.x + dirX[dir], from.y + dirY[dir]}; 
	    if(isValid(to, n) && !isBear[to.x][to.y]) {
              bear.push(to);
              isBear[to.x][to.y] = true;
            }
          }
	}
      }
    }
    int waveSize = bee.size();
    for(int i = 1;i <= waveSize;i++) {
      Point from = bee.front();
      bee.pop();
      for(int dir = 0;dir < 4;dir++) {
	Point to = {from.x + dirX[dir], from.y + dirY[dir]};
	if(isValid(to, n) && mat[to.x][to.y] != 'D') {
          bee.push(to);
	  isBee[to.x][to.y] = true;
	}
      }
    }
  }
  if(isBear[fin.x][fin.y] == true) {
    return true;
  }
  return false;
}

int cautbin(int from, int to, int step, int n) {
  if(from >= to) {
    return from;
  } else {
    int mid = (from + to + 1) / 2;
    if(canBear(n, step, mid)) {
      return cautbin(mid, to, step, n);
    }else {
      return cautbin(from, mid-1, step, n);
    }
  }
}

int main() {

  int n, step;
  cin >> n >> step;
  for(int i = 1;i <= n;i++) {
    for(int j = 1;j <= n;j++) {
      cin >> mat[i][j];
    }
  }
  int ans = cautbin(0, n*n, step, n);
  if(canBear(n, step, ans)) {
    cout << ans << '\n';
  }else {
    cout << "-1\n";
  }
  return 0;
}

• Subtask 1: 100 / 100