結果
問題 | No.5015 Escape from Labyrinth |
ユーザー |
![]() |
提出日時 | 2023-04-13 00:56:22 |
言語 | C++17(gcc12) (gcc 12.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 1,605 ms / 3,000 ms |
コード長 | 8,729 bytes |
コンパイル時間 | 3,877 ms |
コンパイル使用メモリ | 218,480 KB |
実行使用メモリ | 18,880 KB |
スコア | 65,580 |
最終ジャッジ日時 | 2023-04-15 11:41:45 |
合計ジャッジ時間 | 85,437 ms |
ジャッジサーバーID (参考情報) |
judge16 / judge15 |
純コード判定しない問題か言語 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 100 |
ソースコード
#include <bits/stdc++.h>using std::array, std::vector, std::string;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";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;int param = 10000;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;}}int evaluate() const {int res = 0;if (key) {res -= distance[64 * y + x];} else {res -= distance_key[64 * y + x];}res -= block;res *= 10 * D;res += param * score + hp;return res;}// action: 0 to 12// return: is_legalbool advance(const int action) {turn++;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 < 4; action++) {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);std::queue<int> que;distance.fill(N * N);distance[64 * gy + gx] = 0;que.push(64 * gy + gx);while (not que.empty()) {int idx = que.front();que.pop();int y0 = idx / 64, x0 = idx % 64;for (int d = 0; d < 4; d++) {int ny = y0 + dy[d], nx = x0 + dx[d];if (range_out(ny, nx)) continue;int state = S[ny][nx];if (state == '#' or state == 'E') {continue;}if (distance[64 * ny + nx] != N * N) continue;distance[64 * ny + nx] = distance[idx] + 1;que.push(64 * ny + nx);}}distance_key.fill(N * N);distance_key[64 * ky + kx] = distance[64 * ky + kx];que.push(64 * ky + kx);while (not que.empty()) {int idx = que.front();que.pop();int y0 = idx / 64, x0 = idx % 64;for (int d = 0; d < 4; d++) {int ny = y0 + dy[d], nx = x0 + dx[d];if (range_out(ny, nx)) continue;int state = S[ny][nx];if (state == '#' or state == 'E') {continue;}if (distance_key[64 * ny + nx] != N * N) continue;distance_key[64 * ny + nx] = distance_key[idx] + 1;que.push(64 * ny + nx);}}vector<int> ans;while (not board.escaped) {int action = beam_search(board, 100, 4);ans.emplace_back(action);if (action == -1) {ans.clear();break;}board.advance(action);board.after();}if (not board.escaped) {param = 100;board = Board(S, E);while (not board.escaped) {int action = beam_search(board, 100, 4);if (action == -1) {break;}ans.emplace_back(action);board.advance(action);board.after();}}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;}