Submission #1241995

#TimeUsernameProblemLanguageResultExecution timeMemory
1241995NeilPMecho (IOI09_mecho)C++20
30 / 100
1094 ms17068 KiB
#include <iostream> #include <queue> #include <tuple> using namespace std; int n, s; char grid[800][800]; int distb[800][800]; bool vis[800][800]; int dx[] = {1, 0, -1, 0}; int dy[] = {0, 1, 0, -1}; int homex, homey; int honx, hony; bool inside1(pair<int, int> p){ return p.first >= 0 && p.first < n && p.second >= 0 && p.second < n; } bool inside2(pair<int, int> p){ return p.first >= 0 && p.first < n && p.second >= 0 && p.second < n && grid[p.first][p.second] != 'H' && grid[p.first][p.second] != 'T'; } int main() { queue<pair<int, int>> q; cin >> n >> s; for(int i = 0; i < n; i++){ string line; cin >> line; for(int j = 0; j < n; j++){ grid[i][j] = line[j]; distb[i][j] = 2*n; if(grid[i][j] == 'H'){ q.push({i, j}); distb[i][j] = 0; } if(grid[i][j] == 'D'){ homex = i; homey = j; } if(grid[i][j] == 'M'){ honx = i; hony = j; } } } while(!q.empty()){ auto x = q.front(); q.pop(); for(int i = 0; i < 4; i++){ pair<int, int> y = {x.first + dx[i], x.second + dy[i]}; if(inside1(y) && distb[x.first][x.second] + 1 < distb[y.first][y.second]){ distb[y.first][y.second] = distb[x.first][x.second] + 1; q.push({y.first, y.second}); } } } vis[homex][homey] = true; queue<tuple<int, int, int>> deq; // x, y, moves queue<tuple<int, int, int>> deq1; // x, y, moves deq.push({homex, homey, 0}); int mins = distb[homex][homey] - 1; bool stop = false; while(mins >= 0){ while(!deq.empty()){ auto t = deq.front(); if(get<0>(t) == honx && get<1>(t) == hony){ stop = true; break; } deq1.push({get<0>(t), get<1>(t), 0}); deq.pop(); if(get<2>(t) < s){ for(int i = 0; i < 4; i++){ pair<int, int> y = {get<0>(t) + dx[i], get<1>(t) + dy[i]}; if(inside2(y) && !vis[y.first][y.second] && distb[y.first][y.second] > mins){ vis[y.first][y.second] = true; deq.push({y.first, y.second, get<2>(t) + 1}); } } } } if(stop) break; deq = deq1; deq1 = queue<tuple<int, int, int>>(); mins --; } cout << mins << endl; }
#Verdict Execution timeMemoryGrader output
Fetching results...