제출 #654276

#제출 시각아이디문제언어결과실행 시간메모리
654276four_specksMecho (IOI09_mecho)C++17
54 / 100
614 ms2344 KiB
#include <bits/stdc++.h> using namespace std; inline namespace { } // namespace void solve() { int n, s; cin >> n >> s; vector<string> grid(n); for (string &row : grid) cin >> row; vector grass(n, vector<bool>(n, 1)); vector<array<int, 2>> hives; array<int, 2> honey, home; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { char cell = grid[i][j]; if (cell == 'T') grass[i][j] = 0; else if (cell == 'M') honey = {i, j}; else if (cell == 'D') home = {i, j}; else if (cell == 'H') hives.push_back({i, j}); } } auto check = [&](int mid) -> bool { vector bad(n, vector<bool>(n, 0)); queue<array<int, 2>> bees; for (const array<int, 2> &coord : hives) bad[coord[0]][coord[1]] = 1, bees.push(coord); auto mv_bees = [&] { queue<array<int, 2>> bees1; while (!bees.empty()) { auto [x, y] = bees.front(); bees.pop(); for (auto [dx, dy] : {array{0, -1}, array{0, 1}, array{-1, 0}, array{1, 0}}) { int x1 = x + dx, y1 = y + dy; if (0 <= x1 && x1 < n && 0 <= y1 && y1 < n && grass[x1][y1] && array{x1, y1} != home && !bad[x1][y1]) bad[x1][y1] = 1, bees1.push({x1, y1}); } } bees = move(bees1); }; for (int i = 0; i < mid; i++) mv_bees(); vector seen(n, vector<bool>(n, 0)); queue<array<int, 2>> q; if (!bad[honey[0]][honey[1]]) seen[honey[0]][honey[1]] = 1, q.push(honey); auto mv_q = [&] { for (int i = 0; i < s; i++) { queue<array<int, 2>> q1; while (!q.empty()) { auto [x, y] = q.front(); q.pop(); for (auto [dx, dy] : {array{0, -1}, array{0, 1}, array{-1, 0}, array{1, 0}}) { int x1 = x + dx, y1 = y + dy; if (0 <= x1 && x1 < n && 0 <= y1 && y1 < n && grass[x1][y1] && !bad[x1][y1] && !seen[x1][y1]) seen[x1][y1] = 1, q1.push({x1, y1}); } } q = move(q1); } }; while (!q.empty()) { mv_q(); mv_bees(); } return seen[home[0]][home[1]]; }; int lo = -1, hi = n * n; while (lo < hi) { int mid = (lo + hi + 1) / 2; if (check(mid)) lo = mid; else hi = mid - 1; } cout << lo << '\n'; } int main() { ios_base::sync_with_stdio(false), cin.tie(NULL); solve(); return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...