Submission #611686

#TimeUsernameProblemLanguageResultExecution timeMemory
611686BelguteiMecho (IOI09_mecho)C++17
22 / 100
152 ms8808 KiB
#include<bits/stdc++.h> using namespace std; #define ll long long #define ff first #define ss second #define pb push_back #define mk make_pair #define IOS ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int n,m; int b[805][806]; queue<pair<int,int> > q; int stx, sty; int cnt[805][805]; int tmp[805][805]; bool check = 0; char ch[805][805]; int main() { IOS cin >> n >> m; for(int i = 1; i <= n; i ++) { for(int j = 1; j <= n; j ++) { cin >> ch[i][j]; if(ch[i][j] == 'H') { b[i][j] = 1; q.push({i,j}); } if(ch[i][j] == 'M') { stx = i; sty = j; } } } while(q.size() > 0) { int x = q.front().ff; int y = q.front().ss; q.pop(); if(x > 1 && b[x - 1][y] == 0 && ch[x - 1][y] != 'T' && ch[x - 1][y] != 'D') { q.push({x - 1, y}); b[x - 1][y] = b[x][y] + 1; } if(x < n && b[x + 1][y] == 0 && ch[x + 1][y] != 'T' && ch[x + 1][y] != 'D') { q.push({x + 1, y}); b[x + 1][y] = b[x][y] + 1; } if(y > 1 && b[x][y - 1] == 0 && ch[x][y - 1] != 'T' && ch[x][y - 1] != 'D') { q.push({x, y - 1}); b[x][y - 1] = b[x][y] + 1; } if(y < n && b[x][y + 1] == 0 && ch[x][y + 1] != 'T' && ch[x][y + 1] != 'D') { q.push({x, y + 1}); b[x][y + 1] = b[x][y] + 1; } } for(int i = 1; i <= n; i ++) { for(int j = 1; j <= n; j ++) { if(b[i][j] == 0) b[i][j] = 1e9; } } int l = 0; int r = n * n; while(l < r) { int mid = (l + r + 1) / 2; memset(cnt, -1, sizeof(cnt)); while(q.size() > 0) q.pop(); q.push({stx,sty}); cnt[stx][sty] = mid; tmp[stx][sty] = m; bool ok = 0; while(q.size() > 0) { int x = q.front().ff; int y = q.front().ss; q.pop(); int num = cnt[x][y]; int move = tmp[x][y]; if(tmp[x][y] == m) { num ++; move = 0; } move ++; // if(x > 1 && cnt[x - 1][y] == -1 && num < b[x - 1][y] && ch[x - 1][y] != 'T') { if(ch[x - 1][y] == 'D') { // home location ok = 1; break; } cnt[x - 1][y] = num; tmp[x - 1][y] = move; q.push({x - 1, y}); } // if(x < n && cnt[x + 1][y] == -1 && num < b[x + 1][y] && ch[x + 1][y] != 'T') { if(ch[x + 1][y] == 'D') { // home location ok = 1; break; } cnt[x + 1][y] = num; tmp[x + 1][y] = move; q.push({x + 1, y}); } // if(y > 1 && cnt[x][y - 1] == -1 && num < b[x][y - 1] && ch[x][y - 1] != 'T') { if(ch[x][y - 1] == 'D') { // home location ok = 1; break; } cnt[x][y - 1] = num; tmp[x][y - 1] = move; q.push({x, y - 1}); } // if(y < n && cnt[x][y + 1] == -1 && num < b[x][y + 1] && ch[x][y + 1] != 'T') { if(ch[x][y + 1] == 'D') { // home location ok = 1; break; } cnt[x][y + 1] = num; tmp[x][y + 1] = move; q.push({x, y + 1}); } } if(ok == 1) { check = 1; l = mid; } else r = mid - 1; } if(check == 1){ cout << l - 1; } else cout << -1; }
#Verdict Execution timeMemoryGrader output
Fetching results...