제출 #817552

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
817552		Asamai	Mecho (IOI09_mecho)	C++17	43 / 100	134 ms	5076 KiB

mecho

#include <bits/stdc++.h>
 
using namespace std;
 
template<class A, class B> bool maximize(A& x, B y) {if (x < y) return x = y, true; else return false;}
template<class A, class B> bool minimize(A& x, B y) {if (x > y) return x = y, true; else return false;}
 
#define     all(a)                a.begin(), a.end()
#define     pb                    push_back
#define     pf                    push_front
#define     fi                    first
#define     se                    second
 
typedef     long long             ll;
typedef     unsigned long long    ull;
typedef     double                db;
typedef     long double           ld;
typedef     pair<db, db>          pdb;
typedef     pair<ld, ld>          pld;
typedef     pair<int, int>        pii;
typedef     pair<ll, ll>          pll;
typedef     pair<ll, int>         plli;
typedef     pair<int, ll>         pill;
 
const int MAX_N = 800 + 5;
const int dx[] = {0, 0, 1, -1};
const int dy[] = {1, -1, 0, 0};
 
int n, S;
string a[MAX_N];
pii s, t;
int dist[MAX_N][MAX_N];
bool ok[MAX_N][MAX_N];
 
bool inside(int x, int y) {
	return x > 0 && x <= n && y > 0 && y <= n;
}
 
bool check(int mid) {
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			ok[i][j] = false;
		}
	}
 
	queue<pair<pii, int>> q;
	q.push({s, mid * S});
	ok[s.fi][s.se] = true;
	while (!q.empty()) {
		int u = q.front().fi.fi;
		int v = q.front().fi.se;
		int time = q.front().se;
 
		q.pop();
 
		for (int k = 0; k < 4; k++) {
			int x = u + dx[k];
			int y = v + dy[k];
 
			if (inside(x, y) && (a[x][y] == 'G' || a[x][y] == 'D') && !ok[x][y] && dist[x][y] > time) {
				ok[x][y] = true;
				q.push({{x, y}, time + 1});
			}
		}
	}
 
	// for (int i = 1; i <= n; i++) {
	// 	for (int j = 1; j <= n; j++) {
	// 		cout << ok[i][j] << " ";
	// 	}
	// 	cout << '\n';
	// }
 
	return ok[t.fi][t.se];
}
	
signed main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
 
	queue<pii> q;
	cin >> n >> S;
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
		a[i] = ' ' + a[i];
		for (int j = 1; j <= n; j++) {
			if (a[i][j] == 'M') {
				s = {i, j};
			}
			if (a[i][j] == 'D') {
				t = {i, j};
			}
			if (a[i][j] == 'H') {
				q.push({i, j});
				dist[i][j] = 1;
			}
		}
	}
 
	while (!q.empty()) {
		int u = q.front().fi;
		int v = q.front().se;
		q.pop();
		for (int k = 0; k < 4; k++) {
			int x = u + dx[k];
			int y = v + dy[k];
			if (inside(x, y) && (a[x][y] == 'G' || a[x][y] == 'M') && !dist[x][y]) {
				dist[x][y] = dist[u][v] + 1;
				q.push({x, y});
			}
		}
	}
 
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			dist[i][j]--;
			dist[i][j] *= S;
		}
	}
	dist[t.fi][t.se] = 1e9;
 
	int low = 0, high = dist[s.fi][s.se] - 1;
	int ans = -1;
	while (low <= high) {
		int mid = (low + high) >> 1;
		if (check(mid)) {
			ans = mid;
			low = mid + 1;
		}
		else {
			high = mid - 1;
		}
	}
 
	cout << ans;
 
	return 0;
}
 
/*
 
 
*/

• Subtask 1: 43 / 100