제출 #1192902

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1192902		alexscrip	Mecho (IOI09_mecho)	C++20	54 / 100	149 ms	6312 KiB

mecho

#include <bits/stdc++.h>
using namespace std;

int dx[4] = {0, 1, 0, -1};
int dy[4] = {1, 0, -1, 0};

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	
	int n, s; cin >> n >> s;
	
	vector<string> grid(n);
	for (int i = 0; i < n; i++) cin >> grid[i];
	
	vector<vector<int>> bee_time(n, vector<int>(n, -1));
	
	int homex = 0, homey = 0;
	int hpx = 0, hpy = 0;
	queue<pair<int,int>> qb;
	
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (grid[i][j] == 'H') {
				qb.push({i, j});
				bee_time[i][j] = 0;
			} else if (grid[i][j] == 'D') {
				// Home
				homex = i; homey = j;
			} else if (grid[i][j] == 'M') {
				hpx = i; hpy = j;
			}
		}
	}
	
	while (!qb.empty()) {
		int x = qb.front().first, y = qb.front().second;
		qb.pop();
		
		for (int i = 0; i < 4; i++) {
			int nx = dx[i] + x, ny = dy[i] + y;
			
			if (nx >= 0 && nx < n && ny >= 0 && ny < n && bee_time[nx][ny] == -1 && (grid[nx][ny] == 'G' || grid[nx][ny] == 'M')) {
				bee_time[nx][ny] = bee_time[x][y] + 1;
				qb.push({nx, ny});
			}
		}
	}
	
	// BSTA
	int l = 0, r = INT_MAX;
	int ans = -1;
	
	while (l <= r) {
		int mid = l + (r - l) / 2;
		// Run a BFS, see if you can reach home from D
		vector<vector<int>> dist(n, vector<int>(n, -1));
		dist[hpx][hpy] = 0;
		int valid = 0;
		queue<pair<int, int>> q;
		q.push({hpx, hpy});
		
		if (bee_time[hpx][hpy] == -1 || mid < bee_time[hpx][hpy]) {
			while (!q.empty()) {
				int x = q.front().first, y = q.front().second;
				q.pop();
				if (x == homex && y == homey) {
					valid = 1;
					break;
				}
				
				for (int i = 0; i < 4; i++) {
					int nx = dx[i] + x, ny = dy[i] + y;
					if (nx >= 0 && nx < n && ny >= 0 && ny < n && (grid[nx][ny] == 'G' || grid[nx][ny] == 'D') && dist[nx][ny] == -1) {
						int total_dist = mid + ((dist[x][y] + s) / s);
						if (total_dist <= bee_time[nx][ny] || bee_time[nx][ny] == -1) {
							dist[nx][ny] = dist[x][y] + 1;
							q.push({nx, ny});
						}
					}
				}
			}
		}
		
		
		if (valid) {
			ans = mid;
			l = mid + 1;
		} else r = mid - 1;
	}
	
	cout << ans << '\n';
	
	return 0;
}

• Subtask 1: 54 / 100