제출 #710994

#제출 시각아이디문제언어결과실행 시간메모리
710994tgp072Mecho (IOI09_mecho)C++14
100 / 100
240 ms10444 KiB
#include <iostream> #include <fstream> #include <algorithm> #include <vector> #include <stack> #include <queue> #include <math.h> #include <set> #include <unordered_set> #include <map> #include <string> #include <tuple> #include <numeric> #include <climits> #include <bitset> #include <iomanip> #include <random> #include <ctime> using namespace std; typedef long long ll; const ll INF = 1e14; const ll MOD = 1e9 + 7; const ll MAXN = 2e5 + 1; ll fact[MAXN]; void precompute() { fact[0] = 1; for (ll i = 1; i < MAXN; i++) { fact[i] = (i * fact[i - 1]) % MOD; } } ll powmod(ll a, ll b){ a %= MOD; if (a == 0) return 0; ll product = 1; while(b > 0){ if (b&1){ // you can also use b % 2 == 1 product *= a; product %= MOD; --b; } a *= a; a %= MOD; b /= 2; // you can also use b >> 1 } return product; } ll max(ll a, ll b) { if (a > b) { return a; } else { return b; } } ll min(ll a, ll b) { if (a < b) { return a; } else { return b; } } //calculates the inverse of a number mod MOD ll inv(ll a) { return powmod(a, MOD - 2); } struct State{ ll cr, cc, cd; }; ll dr[4] = {0, 1, 0, -1}; ll dc[4] = {1, 0, -1, 0}; void solve(ll ca) { ll n, s; cin >> n >> s; char grid[n][n]; pair<ll, ll> sc; for (ll i = 0; i < n; i++) { for (ll j = 0; j < n; j++) { cin >> grid[i][j]; if (grid[i][j] == 'M') { sc = {i, j}; } } } ll dist[n][n]; for (ll i = 0; i < n; i++) { for (ll j = 0; j < n; j++) { dist[i][j] = INF; } } queue<State> q; for (ll i = 0; i < n; i++) { for (ll j = 0; j < n; j++) { if (grid[i][j] == 'H') { q.push({i, j, 0}); } } } while (!q.empty()) { State cur = q.front(); q.pop(); if (dist[cur.cr][cur.cc] <= cur.cd) { continue; } dist[cur.cr][cur.cc] = cur.cd; for (ll k = 0; k < 4; k++) { ll nr = cur.cr + dr[k]; ll nc = cur.cc + dc[k]; if (nr >= 0 && nr < n && nc >= 0 && nc < n && grid[nr][nc] != 'T' && grid[nr][nc] != 'D' && grid[nr][nc] != 'H') { q.push({nr, nc, cur.cd+1}); } } } /* for (ll i = 0; i < n; i++) { for (ll j = 0; j < n; j++) { if (dist[i][j] == INF) { cout << -1 << " "; continue; } cout << dist[i][j] << " "; } cout << endl; }*/ ll lo = 0; ll hi = INF; lo--; while (lo < hi) { ll mid = lo + (hi - lo + 1)/2; //mid = 2; bool works = false; bool visited[n][n]; for (ll i = 0; i < n; i++) { for (ll j = 0; j < n; j++) { visited[i][j] = false; } } queue<State> q2; q2.push({sc.first, sc.second, s*mid}); while (!q2.empty()) { State cur = q2.front(); q2.pop(); /*if (cur.cr == 3 && cur.cc == 6) { cout << "I AM HERE" << endl; }*/ if (grid[cur.cr][cur.cc] == 'D') { works = true; break; } /*if (cur.cr == 3 && cur.cc == 6) { cout << "I AM HERE" << endl; }*/ ll nummin = cur.cd/s; if (nummin >= dist[cur.cr][cur.cc]) { continue; } if (visited[cur.cr][cur.cc]) { continue; } //cout << cur.cr << " " << cur.cc << endl; visited[cur.cr][cur.cc] = true; for (ll k = 0; k < 4; k++) { ll nr = cur.cr + dr[k]; ll nc = cur.cc + dc[k]; if (nr >= 0 && nr < n && nc >= 0 && nc < n && grid[nr][nc] != 'T') { q2.push({nr, nc, cur.cd+1}); } } } if (works) { lo = mid; } else { hi = mid - 1; } /*cout << works << endl; return;*/ } cout << lo << endl; } int main() { mt19937 rng(0); // Fast IO ios::sync_with_stdio(false); cin.tie(nullptr); /* freopen("gravity.in", "r", stdin); freopen("gravity.out", "w", stdout); */ ll t = 1; //cin >> t; ll co = 0; while (t--) { solve(co); co++; } }
#Verdict Execution timeMemoryGrader output
Fetching results...