제출 #482593

#제출 시각아이디문제언어결과실행 시간메모리
482593danielsuhMecho (IOI09_mecho)C++17
7 / 100
1100 ms65540 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; const int mxN = 805; int N, S; char grid[mxN][mxN], store_grid[mxN][mxN]; int dist[mxN][mxN]; pair<int, int> start, finish; int dx[4] = {-1, 0, 1, 0}; int dy[4] = {0, -1, 0, 1}; bool check(int seconds) { // Can you just simulate the first w seconds and then find the BFS thing? for(auto &x : dist) for(auto &y : x) y = INT_MAX; for(int i = 0; i < N; i++) for(int j = 0; j < N; j++) grid[i][j] = store_grid[i][j]; bool reached_end = 0; for(int i = 0; i < seconds; i++) { vector<pair<int, int>> change; for(int j = 0; j < N; j++) { for(int k = 0; k < N; k++) { if(grid[j][k] == 'H') { for(int it = 0; it < 4; it++) { if(j - 1 >= 0 && grid[j - 1][k] != 'M' && grid[j - 1][k] != 'D' && grid[j - 1][k] != 'T') change.push_back(make_pair(j - 1, k)); if(j + 1 < N && grid[j + 1][k] != 'M' && grid[j + 1][k] != 'D' && grid[j + 1][k] != 'T') change.push_back(make_pair(j + 1, k)); if(k - 1 >= 0 && grid[j][k - 1] != 'M' && grid[j][k - 1] != 'D' && grid[j][k - 1] != 'T') change.push_back(make_pair(j, k - 1)); if(k + 1 < N && grid[j][k + 1] != 'M' && grid[j][k + 1] != 'D' && grid[j][k + 1] != 'T') change.push_back(make_pair(j, k + 1)); } } } } for(auto &x : change) grid[x.first][x.second] = 'H'; } queue<pair<pair<int, int>, int>> q; q.push({make_pair(start.first, start.second), 0}); dist[start.first][start.second] = 0; unordered_map<int, bool> considered; while(!q.empty()) { if(q.front().second % S == 0 && q.front().second != 0 && !considered[q.front().second]) { vector<pair<int, int>> change; for(int j = 0; j < N; j++) { for(int k = 0; k < N; k++) { if(grid[j][k] == 'H') { for(int it = 0; it < 4; it++) { if(j - 1 >= 0 && grid[j - 1][k] != 'M' && grid[j - 1][k] != 'D' && grid[j - 1][k] != 'T') change.push_back(make_pair(j - 1, k)); if(j + 1 < N && grid[j + 1][k] != 'M' && grid[j + 1][k] != 'D' && grid[j + 1][k] != 'T') change.push_back(make_pair(j + 1, k)); if(k - 1 >= 0 && grid[j][k - 1] != 'M' && grid[j][k - 1] != 'D' && grid[j][k - 1] != 'T') change.push_back(make_pair(j, k - 1)); if(k + 1 < N && grid[j][k + 1] != 'M' && grid[j][k + 1] != 'D' && grid[j][k + 1] != 'T') change.push_back(make_pair(j, k + 1)); } } } } for(auto &x : change) grid[x.first][x.second] = 'H'; considered[q.front().second] = true; continue; } int x = q.front().first.first, y = q.front().first.second; int cur_second = q.front().second; q.pop(); if(grid[x][y] == 'H' || grid[x][y] == 'T') continue; if(grid[x][y] == 'D') return true; for(int i = 0; i < 4; i++) { if(x + dx[i] > 0 && y + dy[i] > 0 && x + dx[i] < N && y + dy[i] < N && dist[x][y] + 1 < dist[x + dx[i]][y + dy[i]]) { q.push({make_pair(x + dx[i], y + dy[i]), cur_second + 1}); dist[x + dx[i]][y + dy[i]] = dist[x][y] + 1; } } } return false; } int bin_search() { int lo = 0, hi = N * N; while(lo < hi) { int mid = (lo + hi + 1) / 2; if(check(mid)) { lo = mid; }else { hi = mid - 1; } } return lo; } void solve() { cin >> N >> S; for(int i = 0; i < N; i++) { for(int j = 0; j < N; j++) { cin >> grid[i][j]; store_grid[i][j] = grid[i][j]; if(grid[i][j] == 'M') { start.first = i, start.second = j; }else if(grid[i][j] == 'D') { finish.first = i, finish.second = j; } } } cout << bin_search() << "\n"; } int32_t main() { ios::sync_with_stdio(false); cin.tie(nullptr); int T = 1; // cin >> T; for(int i = 1; i <= T; ++i) { solve(); } }

컴파일 시 표준 에러 (stderr) 메시지

mecho.cpp: In function 'bool check(int)':
mecho.cpp:21:10: warning: unused variable 'reached_end' [-Wunused-variable]
   21 |     bool reached_end = 0;
      |          ^~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...