# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
697458 | europium | Mecho (IOI09_mecho) | C++17 | 176 ms | 6856 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
// - 9/2/23
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <numeric>
#include <cmath>
#include <iterator>
#include <set>
#include <map>
#include <math.h>
#include <iomanip>
#include <unordered_set>
#include <queue>
#include <climits>
using namespace std;
// clang++ -std=c++17 IOI2009_mecho.cpp && ./a.out
using ll = long long;
const int INF = 1e9;
const int dx[] {0, 1, 0, -1};
const int dy[] {1, 0, -1, 0};
int n, s;
int start_x, start_y, end_x, end_y;
vector<vector<char>> grid;
vector<vector<int>> bee;
bool valid(int x, int y){
return (x >= 0 && x < n && y >= 0 && y < n);
}
void get_bee_dist(){
queue<tuple<int,int,int>> q;
for (int i = 0; i < n; i++){
for (int j = 0; j < n; j++){
if (grid[i][j] == 'H'){
bee[i][j] = 0;
q.push({i, j, 0});
}
}
}
while (!q.empty()){
int x, y, d;
tie(x, y, d) = q.front();
q.pop();
for (int k = 0; k < 4; k++){
int i = x + dx[k], j = y + dy[k];
if (!valid(i, j) || grid[i][j] == 'T' || grid[i][j] == 'D' || bee[i][j] <= d + 1) continue;
bee[i][j] = min(bee[i][j], d + 1);
q.push({i, j, d + 1});
}
}
}
bool f(int p){
vector<vector<int>> mecho(n, vector<int> (n, INF));
queue<tuple<int,int,int>> q;
mecho[start_x][start_y] = s;
q.push({start_x, start_y, s});
if (p + 1 > bee[start_x][start_y]) return true;
while (!q.empty()){
int x, y, d;
tie(x, y, d) = q.front();
q.pop();
for (int k = 0; k < 4; k++){
int i = x + dx[k], j = y + dy[k];
if (!valid(i, j) || grid[i][j] == 'T' || mecho[i][j] <= d + 1) continue;
if ((i != end_x || j != end_y) && ((d + 1) / s) + p > bee[i][j]) continue;
mecho[i][j] = min(mecho[i][j], d + 1);
q.push({i, j, d + 1});
}
}
// cout << p << '\n';
//
// for (int i = 0; i < n; i++){
// for (int j = 0; j < n; j++) cout << (mecho[i][j] / s) + p << ' ';
// cout << '\n';
// }
return mecho[end_x][end_y] == INF;
}
void solve(){
cin >> n >> s;
grid.resize(n, vector<char>(n));
bee.resize(n, vector<int> (n, INF));
for (int i = 0; i < n; i++){
for (int j = 0; j < n; j++){
cin >> grid[i][j];
if (grid[i][j] == 'M') {start_x = i; start_y = j;}
if (grid[i][j] == 'D') {end_x = i; end_y = j;}
}
}
get_bee_dist();
int l = -1, r = n * n, ans, mid;
while (l < r){
mid = l + (r - l) / 2;
f(mid) ? r = mid : l = mid + 1;
}
ans = l;
// for (int i = 0; i < n; i++){
// for (int j = 0; j < n; j++) cout << bee[i][j] << ' ';
// cout << '\n';
// }
cout << ans - 1;
cout << '\n';
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
// freopen("input.txt", "r", stdin);
solve();
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |