Submission #607292

#	Time	Username	Problem	Language	Result	Execution time	Memory
607292		beaboss	Mecho (IOI09_mecho)	C++14	13 / 100	100 ms	11740 KiB

mecho

#include <bits/stdc++.h>

using namespace std;

int main() {
	int n, s;

	cin >> n>> s;

	vector<vector<char> > grid(n, vector<char>(n));
	queue<pair<int ,int> > q1;
	queue<pair<int ,int> > q2;
	pair<int ,int> home;
	pair<int ,int> start;


	vector<vector<int> > hdist(n, vector<int>(n, -1));
	vector<vector<int> > mdist(n, vector<int>(n, -1));

	for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) {
		cin >> grid[i][j];
		if (grid[i][j] == 'H') {
			q1.push({i, j});
			hdist[i][j] = 0;
		}
		else if (grid[i][j] == 'M') {
			q2.push({i, j});
			mdist[i][j] = 0;
			start = {i, j};

		}
		else if (grid[i][j] == 'D') home = {i, j};
	}

	
	vector<int> dx = {1, -1, 0, 0};
	vector<int> dy = {0, 0, -1, 1};
	while (!q1.empty() && hdist[home.first][home.second] == -1) {
		pair<int, int> curr = q1.front();
		q1.pop();

		for (int i = 0; i < 4; i++) {
			int x = curr.first + dx[i];
			int y = curr.second + dy[i];
			if (x >= 0 && x < n && y >= 0 && y < n) {
				if (hdist[x][y] == -1 && grid[x][y] == 'G') {
					hdist[x][y] = hdist[curr.first][curr.second] + s;
					q1.push({x, y});
					
				}
			}
		}

	}

	vector<vector<pair<int, int> > > parent(n, vector<pair<int, int> >(n, {-1, -1}));

	while (!q2.empty() && mdist[home.first][home.second] == -1) {
		pair<int, int> curr = q2.front();
		q2.pop();

		for (int i = 0; i < 4; i++) {
			int x = curr.first + dx[i];
			int y = curr.second + dy[i];
			if (x >= 0 && x < n && y >= 0 && y < n) {
				if (mdist[x][y] == -1 && (grid[x][y] == 'G' || grid[x][y] == 'D') && (hdist[x][y] > mdist[curr.first][curr.second] + 1 || hdist[x][y ] == -1)) {
					mdist[x][y] = mdist[curr.first][curr.second] + 1;
					q2.push({x, y});
					
					parent[x][y] = {curr.first, curr.second};
				}
			}
		}

	}
	int ans = 100000000;
	pair<int ,int> current = home;
	// cout << mdist[home.first][home.second] << endl;
	if (mdist[home.first][home.second] == -1) {
		cout << -1 << endl;
		return 0;
	}

	while (current != start) {
		int x = current.first;
		int y = current.second;
		if (hdist[x][y] != -1) {
			// cout << x << y << hdist[x][y] << endl;
			ans = min(ans, hdist[x][y]-mdist[x][y]);
		}
		current = parent[x][y];
	}
	// for (int i = 0; i < 4; i++) {
	// 	int x = home.first + dx[i];
	// 	int y = home.second + dy[i];
	// 	if (x >= 0 && x < n && y >= 0 && y < n && grid[x][y] != 'T') {
	// 		ans = max(hdist[x][y] - mdist[x][y], ans);
	// 		cout << mdist[x][y] << hdist[x][y] << x << y << endl;
	// 	}
	// }
	cout << ans/3 << endl;


	
	
}

• Subtask 1: 13 / 100