#include #include #include #include #include #include #include struct int_plus_pi { // int_part + pi / 4 * pi_part int int_part = 0, pi_part = 0; constexpr int_plus_pi operator+(const int_plus_pi& rhs) const { return int_plus_pi {int_part + rhs.int_part, pi_part + rhs.pi_part}; } constexpr long double val() const { return int_part + (M_PI / 4.0L) * pi_part; } constexpr bool operator<(const int_plus_pi& rhs) const { if (int_part == rhs.int_part) return pi_part < rhs.pi_part; if (pi_part == rhs.pi_part) return int_part < rhs.int_part; return val() < rhs.val(); } }; void solve() { int H, W; std::cin >> H >> W; std::vector S(H); for (int i = 0; i < H; i++) std::cin >> S[i]; constexpr int INF = 1000000005; constexpr int dy[] = {0, 1, 0, -1}; constexpr int dx[] = {1, 0, -1, 0}; // cost[i][j][k] // k = 0: horizontal // k = 1: vertical std::vector cost(H, std::vector(W, std::vector(2, {INF, INF}))); cost[0][0][0] = cost[0][0][1] = {0, 4}; using pq_elem = std::tuple; std::priority_queue, std::greater> pq; if (1 < H && S[1][0] == '.') { cost[1][0][1] = {4, 4}; pq.emplace(int_plus_pi {4, 4}, 1, 0, 1); } if (1 < W && S[0][1] == '.') { cost[0][1][0] = {4, 4}; pq.emplace(int_plus_pi {4, 4}, 0, 1, 0); } while (!pq.empty()) { const auto [ccost, cy, cx, cd] = pq.top(); pq.pop(); // right: 0, up: 1, left: 2, down: 3 for (int direction = 0; direction < 4; direction++) { const int ny = cy + dy[direction], nx = cx + dx[direction]; if (ny < 0 || nx < 0 || H <= ny || W <= nx || S[ny][nx] == '#') continue; int_plus_pi new_cost; if (cd == (direction & 1)) // same direction new_cost = ccost + int_plus_pi {4, 0}; else // different direction new_cost = ccost + int_plus_pi {3, 1}; if (new_cost < cost[ny][nx][direction & 1]) { cost[ny][nx][direction & 1] = new_cost; pq.emplace(new_cost, ny, nx, direction & 1); } } } const int_plus_pi res = *std::min_element(cost[H - 1][W - 1].cbegin(), cost[H - 1][W - 1].cend()); if (res < int_plus_pi {INF, INF}) std::cout << res.int_part << ' ' << res.pi_part / (int[]) {4, 1, 2, 1}[res.pi_part % 4] << ' ' << (int[]) {1, 4, 2, 4}[res.pi_part % 4] << '\n'; else std::cout << -1 << '\n'; } int main() { std::ios_base::sync_with_stdio(false); std::cin.tie(nullptr); solve(); }

提出日時
ユーザー	naskya
言語	C++ (GCC 9.3.0)
結果	AC
実行時間	6 ms
メモリ	129528 kb

テストケース名	結果	実行時間	メモリ
01.txt	AC	4 ms	129528 kb
02.txt	AC	3 ms	129528 kb
03.txt	AC	3 ms	129528 kb
04.txt	AC	3 ms	129528 kb
05.txt	AC	3 ms	129528 kb
06.txt	AC	3 ms	129528 kb
07.txt	AC	3 ms	129528 kb
08.txt	AC	4 ms	129528 kb
09.txt	AC	6 ms	129528 kb
sample_01.txt	AC	3 ms	129528 kb
sample_02.txt	AC	3 ms	129528 kb
sample_03.txt	AC	3 ms	129528 kb

lazy robotic vacuum cleaner

コンパイルエラー