結果
問題 | No.5015 Escape from Labyrinth |
ユーザー |
![]() |
提出日時 | 2023-04-13 02:57:29 |
言語 | C++17(gcc12) (gcc 12.3.0 + boost 1.87.0) |
結果 |
RE
|
実行時間 | - |
コード長 | 10,222 bytes |
コンパイル時間 | 2,806 ms |
コンパイル使用メモリ | 224,692 KB |
実行使用メモリ | 9,340 KB |
スコア | 39,460 |
最終ジャッジ日時 | 2023-04-15 11:44:06 |
合計ジャッジ時間 | 208,083 ms |
ジャッジサーバーID (参考情報) |
judge13 / judge14 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 95 RE * 5 |
ソースコード
#include <bits/stdc++.h>using std::array, std::vector, std::string;using vertex = std::pair<int, int>;auto start = std::chrono::steady_clock::now();auto elapsed() { return (std::chrono::steady_clock::now() - start).count(); }constexpr int N = 60; // 迷宮の大きさconstexpr int max_hp = 1500; // 初期体力constexpr int dy[4] = {-1, 1, 0, 0};constexpr int dx[4] = {0, 0, -1, 1};constexpr auto dir = "UDLR";constexpr int inf = 1e9;enum { EMPTY, BLOCK, E2, E3, E4, E5, WALL, JEWELL, FIRE, KEY, GOAL };// 範囲外かどうかbool range_out(size_t y, size_t x) { return x >= N or y >= N; }// 探知機の情報struct enemy {int y, x, d;enemy(int y, int x, int d) : y(y), x(x), d(d) {}};int D, H;int ky, kx;int gy, gx;array<int, 64 * 64 * 64> cost, distance, distance_key;// 盤面の情報struct Board {array<int, 64 * 64> board;int score = 0;int fire = 0;int hp = max_hp;int block = 0;bool key = false;bool escaped = false;int y, x;int turn = 0;int first_action = -1;Board(const vector<string> &S, const vector<enemy> &E) {board.fill(EMPTY);for (int i = 0; i < N; i++) {for (int j = 0; j < N; j++) {const int idx = 64 * i + j;switch (S[i][j]) {case '#':board[idx] = WALL;break;case 'J':board[idx] = JEWELL;break;case 'F':board[idx] = FIRE;break;case 'K':board[idx] = KEY;ky = i;kx = j;break;case 'G':board[idx] = GOAL;gy = i;gx = j;break;case 'S':y = i;x = j;break;}}}for (const auto &[i, j, d] : E) {board[64 * i + j] = d;}}double evaluate() const {if (escaped) return score;int dist = distance_key[64 * 64 * turn + 64 * y + x];if (key) {dist = distance[64 * 64 * turn + 64 * y + x];}double res = hp - dist;if (res <= 0) return -inf;return score + (0.1 * hp + 0.0001 * res) / (0.5 * D + 1.0);}// action: 0 to 12// return: is_legalbool advance(const int action) {turn++;if (turn == 60) turn = 0;const int d = action & 3;int ny = y + dy[d], nx = x + dx[d];if (action < 4) { // moveif (range_out(ny, nx)) return false;int &state = board[64 * ny + nx];y = ny;x = nx;if (state == WALL or state == BLOCK or(2 <= state and state <= 5)) {return false;} else if (state == KEY) {key = true;state = EMPTY;} else if (state == JEWELL) {score++;state = EMPTY;} else if (state == FIRE) {fire++;state = EMPTY;} else if (state == GOAL and key) {escaped = true;}return true;} else if (action < 8) { // blockif (range_out(ny, nx)) return false;if (board[64 * ny + nx] >= 2) return false;block -= board[64 * ny + nx];board[64 * ny + nx] = 1 - board[64 * ny + nx];block += board[64 * ny + nx];return true;} else if (action < 12) { // fireif (fire == 0) return false;while (not range_out(ny, nx)) {int state = board[64 * ny + nx];if (2 <= state and state <= 5) { // enemyboard[64 * ny + nx] = EMPTY;fire--;return true;} else if (state == WALL or state == BLOCK) {return false;}ny += dy[d];nx += dx[d];}return false;} else {return true;}}void after() {for (int d = 0; d < 4; d++) {int y_next = y + dy[d], x_next = x + dx[d];while (not range_out(y_next, x_next)) {int state = board[64 * y_next + x_next];if (2 <= state and state <= 5) { // enemyif (turn % state == 0) hp -= D;break;}if (state == WALL or state == BLOCK) break;y_next += dy[d];x_next += dx[d];}}hp--;}};bool operator<(const Board &a, const Board &b) {return a.evaluate() < b.evaluate();}int beam_search(const Board &board, const int beam_width,const int beam_depth) {std::priority_queue<Board> beam;Board best_board{board};beam.emplace(board);for (int t = 0; t < beam_depth; t++) {std::priority_queue<Board> next_beam;for (int i = 0; i < beam_width; i++) {if (beam.empty()) break;Board board_now{beam.top()};beam.pop();for (int action = 0; action < 13; action++) {if (4 <= action and action < 8) continue;Board board_next{board_now};if (not board_next.advance(action)) continue;if (not board_next.escaped) {board_next.after();}if (board_next.hp <= 0) continue;if (t == 0) {board_next.first_action = action;}next_beam.emplace(board_next);}}beam = next_beam;best_board = beam.top();if (best_board.escaped) break;}return best_board.first_action;}int main() {int N;// 入力の受け取りstd::cin >> N >> D >> H;vector<string> S(N);for (int i = 0; i < N; i++) std::cin >> S[i];int M;std::cin >> M;vector<enemy> E;for (int i = 0; i < M; i++) {int y, x, d;std::cin >> y >> x >> d;E.emplace_back(y, x, d);}Board board(S, E);cost.fill(1);for (int turn = 0; turn < 60; turn++) {for (int y = 0; y < N; y++) {for (int x = 0; x < N; x++) {for (int d = 0; d < 4; d++) {int ny = y + dy[d], nx = x + dx[d];while (not range_out(ny, nx)) {int state = board.board[64 * ny + nx];if (2 <= state and state <= 5) { // enemyif (turn % state == 0) {cost[64 * 64 * turn + 64 * y + x] += D;}break;}if (state == WALL or state == BLOCK) break;ny += dy[d];nx += dx[d];}}}}}std::priority_queue<vertex, vector<vertex>, std::greater<vertex>> que;distance.fill(inf);for (int turn = 0; turn < 60; turn++) {que.emplace(0, 64 * 64 * turn + 64 * gy + gx);}while (not que.empty()) {auto [d0, idx] = que.top();que.pop();if (distance[idx] <= d0) continue;distance[idx] = d0;int turn = idx / (64 * 64), y0 = idx % (64 * 64) / 64, x0 = idx % 64;int state = S[y0][x0];if (state == '#' or state == 'E') {continue;}int nt = turn > 0 ? turn - 1 : 59;for (int d = 0; d < 4; d++) {int ny = y0 + dy[d], nx = x0 + dx[d];if (range_out(ny, nx)) continue;int n_idx = 64 * 64 * nt + 64 * ny + nx;int nd = distance[idx] + cost[idx];if (state == 'G') {nd = distance[idx];}if (distance[n_idx] <= nd) continue;que.emplace(nd, n_idx);}que.emplace(distance[idx] + cost[idx], 64 * 64 * nt + 64 * y0 + x0);}distance_key.fill(inf);for (int turn = 0; turn < 60; turn++) {que.emplace(distance[64 * 64 * turn + 64 * ky + kx],64 * 64 * turn + 64 * ky + kx);}while (not que.empty()) {auto [d0, idx] = que.top();que.pop();if (distance_key[idx] <= d0) continue;distance_key[idx] = d0;int turn = idx / (64 * 64), y0 = idx % (64 * 64) / 64, x0 = idx % 64;int state = S[y0][x0];if (state == '#' or state == 'E') {continue;}int nt = turn > 0 ? turn - 1 : 59;for (int d = 0; d < 4; d++) {int ny = y0 + dy[d], nx = x0 + dx[d];if (range_out(ny, nx)) continue;int n_idx = 64 * 64 * nt + 64 * ny + nx;int nd = distance_key[idx] + cost[idx];if (distance_key[n_idx] <= nd) continue;que.emplace(nd, n_idx);}que.emplace(distance_key[idx] + cost[idx], 64 * 64 * nt + 64 * y0 + x0);}vector<int> ans;while (not board.escaped) {int action = beam_search(board, 5, 5);ans.emplace_back(action);assert(action != -1);board.advance(action);board.after();// if (board.turn % 60 == 0) std::cerr << board.evaluate() << std::endl;}for (auto &&action : ans) {if (action < 4) {std::cout << "M " << dir[action] << std::endl;} else if (action < 8) {std::cout << "B " << dir[action & 3] << std::endl;} else if (action < 12) {std::cout << "F " << dir[action & 3] << std::endl;} else {std::cout << "S" << std::endl;}}return 0;}