Submission #607297

#TimeUsernameProblemLanguageResultExecution timeMemory
607297beabossMecho (IOI09_mecho)C++14
26 / 100
86 ms21172 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; int main() { ll n, s; cin >> n>> s; vector<vector<char> > grid(n, vector<char>(n)); queue<pair<ll ,ll> > q1; queue<pair<ll ,ll> > q2; pair<ll ,ll> home; pair<ll ,ll> start; vector<vector<ll> > hdist(n, vector<ll>(n, -1)); vector<vector<ll> > mdist(n, vector<ll>(n, -1)); for (ll i = 0; i < n; i++) for (ll 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<ll> dx = {1, -1, 0, 0}; vector<ll> dy = {0, 0, -1, 1}; while (!q1.empty() && hdist[home.first][home.second] == -1) { pair<ll, ll> curr = q1.front(); q1.pop(); for (ll i = 0; i < 4; i++) { ll x = curr.first + dx[i]; ll 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<ll, ll> > > parent(n, vector<pair<ll, ll> >(n, {-1, -1})); while (!q2.empty() && mdist[home.first][home.second] == -1) { pair<ll, ll> curr = q2.front(); q2.pop(); for (ll i = 0; i < 4; i++) { ll x = curr.first + dx[i]; ll 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}; } } } } ll ans = 100000000; pair<ll ,ll> current = home; // cout << mdist[home.first][home.second] << endl; if (mdist[home.first][home.second] == -1) { cout << -1 << endl; return 0; } while (current != start) { ll x = current.first; ll 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 (ll i = 0; i < 4; i++) { // ll x = home.first + dx[i]; // ll 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/s << endl; }
#Verdict Execution timeMemoryGrader output
Fetching results...