| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 953337 | snowman | Mecho (IOI09_mecho) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <iostream>
#include <vector>
#include <queue>
#include <unordered_set>
using namespace std;
struct Cell {
int x, y;
Cell(int _x, int _y) : x(_x), y(_y) {}
};
bool isValid(int x, int y, int n) {
return x >= 0 && x < n && y >= 0 && y < n;
}
int bfs(vector<string>& forest, Cell start, Cell home, int max_steps) {
int n = forest.size();
vector<pair<int, int>> directions = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
unordered_set<int> visited;
queue<pair<Cell, int>> q;
q.push({start, 0});
visited.insert(start.x * n + start.y);
while (!q.empty()) {
Cell current = q.front().first;
int steps = q.front().second;
q.pop();
if (current.x == home.x && current.y == home.y)
return steps;
if (steps >= max_steps)
return -1;
for (auto& dir : directions) {
int nx = current.x + dir.first;
int ny = current.y + dir.second;
if (isValid(nx, ny, n) && forest[nx][ny] != 'T' && visited.find(nx * n + ny) == visited.end()) {
visited.insert(nx * n + ny);
q.push({{nx, ny}, steps + 1});
}
}
}
return -1;
}
int findMaxHoneyTime(vector<string>& forest, Cell start, Cell home, int max_steps) {
int max_time = -1;
unordered_set<int> bees_spread;
int n = forest.size();
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
if (forest[i][j] == 'H')
bees_spread.insert(i * n + j);
}
}
for (int i = 1; i <= max_steps; ++i) {
int time_taken = bfs(forest, start, home, i);
if (time_taken == -1)
break;
max_time = max(max_time, time_taken);
unordered_set<int> temp;
for (auto& cell : bees_spread) {
int x = cell / n;
int y = cell % n;
for (auto& dir : {{0, 1}, {0, -1}, {1, 0}, {-1, 0}}) {
int nx = x + dir.first;
int ny = y + dir.second;
if (isValid(nx, ny, n) && forest[nx][ny] != 'T')
temp.insert(nx * n + ny);
}
}
bees_spread.insert(temp.begin(), temp.end());
}
return max_time;
}
int main() {
int N, S;
cin >> N >> S;
vector<string> forest(N);
for (int i = 0; i < N; ++i)
cin >> forest[i];
Cell start, home;
for (int i = 0; i < N; ++i) {
for (int j = 0; j < N; ++j) {
if (forest[i][j] == 'M')
start = {i, j};
else if (forest[i][j] == 'D')
home = {i, j};
}
}
int max_time = findMaxHoneyTime(forest, start, home, S);
cout << max_time << endl;
return 0;
}