# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
482593 | danielsuh | Mecho (IOI09_mecho) | C++17 | 1100 ms | 65540 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#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) 메시지
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |