Submission #153020

#TimeUsernameProblemLanguageResultExecution timeMemory
153020tselmegkhMecho (IOI09_mecho)C++14
20 / 100
1092 ms7012 KiB
#include<bits/stdc++.h> using namespace std; const int N = 805, inf = 1e9; string a[N]; int d[N][N], dis[N][N], n, s; bool vis[N][N]; pair<int, int> st, en; int mx = 0; int movex[] = {1, 0, -1, 0}; int movey[] = {0, 1, 0, -1}; void fill(){ for(int i = 0; i < 801; i++){ for(int j = 0; j < 801; j++){ d[i][j] = inf; } } } bool check(int i, int j, bool which){ if(which == 1) { if(i >= 0 && i < n && j >= 0 && j < n && (a[i][j] == 'G' || a[i][j] == 'D') && !vis[i][j]){ return 1; } return 0; } else{ if(i >= 0 && i < n && j >= 0 && j < n && a[i][j] == 'G' && !vis[i][j]){ return 1; } return 0; } } void bfs(int i, int j){ memset(vis, 0, sizeof vis); memset(dis, 0, sizeof dis); queue<pair<int, int>> q; dis[i][j] = 0; vis[i][j] = 1; q.push({i, j}); while(!q.empty()){ pair<int, int> u = q.front(); q.pop(); for(int i1 = 0; i1 < 4; i1++){ int x = movex[i1], y = movey[i1]; if(check(u.first + x, u.second + y, 0)){ vis[u.first + x][u.second + y] = 1; dis[u.first + x][u.second + y] = dis[u.first][u.second] + 1; d[u.first + x][u.second + y] = min(d[u.first + x][u.second + y], dis[u.first + x][u.second + y]); q.push({u.first + x, u.second + y}); mx = max(mx, d[u.first + x][u.second + y]); } } } } bool possible(int x){ int cur = x; memset(vis, 0, sizeof vis); queue<pair<pair<int, int>, pair<int,int>>> q; q.push({{st.first, st.second}, {cur, s}}); vis[st.first][st.second] = 1; while(!q.empty()){ auto k = q.front(); q.pop(); int u = k.first.first, v = k.first.second, chargesleft = k.second.second; int now = k.second.first; for(int i = 0; i < 4; i++){ if(check(u + movex[i], v + movey[i], 1)){ if(d[u + movex[i]][v + movey[i]] > now){ if(chargesleft > 1){ q.push({{u + movex[i], v + movey[i]}, {now, chargesleft - 1}}); }else{ q.push({{u + movex[i], v + movey[i]}, {now + 1, s}}); } vis[u + movex[i]][v + movey[i]] = 1; } } } } /*cout << "x : " << x << '\n'; for(int i = 0; i < n; i++){ for(int j = 0; j < n; j++){ cout << vis[i][j]; } cout << '\n'; }*/ if(vis[en.first][en.second])return 1; return 0; } int main(){ cin >> n >> s; fill(); for(int i = 0; i < n; i++){ cin >> a[i]; } for(int i = 0; i < n; i++){ for(int j = 0; j < n; j++){ if(a[i][j] == 'H'){ bfs(i, j); } if(a[i][j] == 'M'){ st.first = i; st.second = j; } if(a[i][j] == 'D'){ en.first = i; en.second = j; } } } /*for(int i = 0; i < n; i++){ for(int j = 0; j < n; j++){ if(d[i][j] != inf)cout << d[i][j]; else cout << 0; } cout << '\n'; }*/ int l = 0, r = mx; while(l != r){ int mid = l + (r - l + 1) / 2; if(possible(mid)){ l = mid; }else{ r = mid - 1; } } cout << l << '\n'; }
#Verdict Execution timeMemoryGrader output
Fetching results...