제출 #393071

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
393071		ngpin04	Mecho (IOI09_mecho)	C++14	84 / 100	713 ms	7024 KiB

mecho

#include <bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
using namespace std;
const int N = 805; 
const int oo = 1e9;
const int dx[] = {1, 0, -1, 0}, dy[] = {0, 1, 0, -1};

char a[N][N];

pair <int, int> s,t;

int bee[N][N];
int dis[N][N];
int n,d;

bool ok(int i, int j) {
	return a[i][j] != 'T' && min(i, j) > 0 && max(i, j) <= n;
}

bool solve(int x, queue <pair <int, int>> q) {
	for (int i = 1; i <= n; i++)
	for (int j = 1; j <= n; j++) {
		if (a[i][j] != 'H')
			bee[i][j] = oo;
		if (a[i][j] != 'M')
			dis[i][j] = oo;
	}

	int fir = -1;
	while (q.size()) {
		int i = q.front().fi;
		int j = q.front().se;
		if (fir < 0)
			fir = bee[i][j];
		if (bee[i][j] - fir == x)
			break;
		q.pop();

		for (int dir = 0; dir < 4; dir++) {
			int u = i + dx[dir];
			int v = j + dy[dir];
			if (ok(u, v) && bee[u][v] == oo) {
				bee[u][v] = bee[i][j] + 1;
				q.push(mp(u, v));
			}
		}
	}

	if (bee[s.fi][s.se] < oo)
		return false;

	queue <pair <int, int>> qq;
	qq.push(s);
	while (qq.size()) {
		fir = -1;
		while (qq.size()) {
			int i = qq.front().fi;
			int j = qq.front().se;
			if (fir < 0)
				fir = dis[i][j];
			if (dis[i][j] - fir == d)
				break;
			qq.pop();

			if (bee[i][j] < oo)
				continue;

			for (int dir = 0; dir < 4; dir++) {
				int u = i + dx[dir];
				int v = j + dy[dir];
				if (ok(u, v) && bee[u][v] == oo && dis[u][v] == oo) {
					dis[u][v] = dis[i][j] + 1;
					qq.push(mp(u, v));
				}
			}
		}

		fir = -1;
		while (q.size()) {
			int i = q.front().fi;
			int j = q.front().se;
			if (fir < 0)
				fir = bee[i][j];
			if (bee[i][j] - fir == 1)
				break;
			q.pop();

			for (int dir = 0; dir < 4; dir++) {
				int u = i + dx[dir];
				int v = j + dy[dir];
				if (ok(u, v) && bee[u][v] == oo) {
					bee[u][v] = bee[i][j] + 1;
					q.push(mp(u, v));
				}
			}
		}
	}
	return dis[t.fi][t.se] < oo;
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cin >> n >> d;

	queue <pair <int, int>> q;
	for (int i = 1; i <= n; i++)
	for (int j = 1; j <= n; j++) {
		cin >> a[i][j];
		if (a[i][j] == 'H') 
			q.push(mp(i, j));
		
		if (a[i][j] == 'M') 
			s = mp(i, j);
	
		if (a[i][j] == 'D')
			t = mp(i, j);
	}
	
	int lo = -1;
	int hi = 1e9;
	while (hi - lo > 1) {
		int mid = (lo + hi) >> 1;
		if (solve(mid, q))
			lo = mid;
		else 
			hi = mid;
	}
	cout << lo;
	return 0;
}

• Subtask 1: 84 / 100