제출 #712197

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
712197		dubabuba	Mecho (IOI09_mecho)	C++14	100 / 100	519 ms	5320 KiB

mecho

#include <bits/stdc++.h>
using namespace std;
 
int di[] = {1, -1, 0, 0};
int dj[] = {0, 0, -1, 1};
 
typedef pair<int, int> pii;
#define ff first
#define ss second
 
const int mxn = 808;
char mp[mxn][mxn];
bool vs[mxn][mxn];
int bee[mxn][mxn];
int n, s, Si, Sj, Di, Dj;
 
bool can(int i, int j) {
	if(mp[i][j] == 'T') return false;
	if(mp[i][j] == 'H') return false;
	return true;
}
 
bool bfs(int M) {
	priority_queue<pair<int, pii>> pq;
	pq.push({0, {Si, Sj}});
 
	memset(vs, 0, sizeof vs);
	vs[Si][Sj] = true;
 
	while(pq.size()) {
		int k = -pq.top().ff;
		int i = pq.top().ss.ff;
		int j = pq.top().ss.ss;
		pq.pop();
 
		if(i == Di && j == Dj) return true;
 
		int minute = k / s;
		if(minute + M >= bee[i][j]) continue;
 
		// cout << minute << ": (" << k << ") " << i << ' ' << j << " - " << bee[i][j] << '\n';
 
		for(int t = 0; t < 4; t++) {
			int I = i + di[t];
			int J = j + dj[t];
 
			if(!vs[I][J] && can(I, J)) {
				vs[I][J] = 1;
				pq.push({-(k + 1), {I, J}});
				// cout << " > " << I << ' ' << J << '\n';
			}
		}
	}
	return false;
}
 
priority_queue<pair<int, pii>> pq;
void beefs() {
	memset(bee, -1, sizeof bee);
 
	while(pq.size()) {
		int k = -pq.top().ff;
		int i = pq.top().ss.ff;
		int j = pq.top().ss.ss;
		pq.pop();
 
		bee[i][j] = k;
 
		for(int t = 0; t < 4; t++) {
			int I = i + di[t];
			int J = j + dj[t];
 
			if(!vs[I][J] && mp[I][J] != 'T' && mp[I][J] != 'D') {
				vs[I][J] = true;
				pq.push({-(k + 1), {I, J}});
			}
		}
	}
}
 
int main() {
	cin >> n >> s;
	for(int i = 1; i <= n; i++)
	for(int j = 1; j <= n; j++) {
		cin >> mp[i][j];
 
		if(mp[i][j] == 'H') {
			pq.push({0, {i, j}});
			vs[i][j] = true;
		}
 
		if(mp[i][j] == 'M') {
			Si = i;
			Sj = j;
		}
 
		if(mp[i][j] == 'D') {
			Di = i;
			Dj = j;
		}
	}
 
	for(int i = 0; i <= n + 1; i++)
	mp[i][0] = mp[i][n + 1] = mp[0][i] = mp[n + 1][i] = 'T';
 
	beefs();
 
	// for(int i = 1; i <= n; i++) {
	// 	for(int j = 1; j <= n; j++)
	// 		cout << mp[i][j] << ' ';
	// 	cout << '\n';
	// }
 
	if(!bfs(0)) {
		cout << -1 << '\n';
		return 0;
	}
 
	int L = 0, R = n * n + 1;
	while(R - L > 1) {
		int M = (L + R) / 2;
		// cout << L << ' ' << R << ": " << M << '\n';
		if(bfs(M)) L = M;
		else R = M;
	}
 
	cout << L << '\n';
	return 0;
}

• Subtask 1: 100 / 100