結果

問題 No.5015 Escape from Labyrinth
ユーザー trineutrontrineutron
提出日時 2023-04-10 04:27:42
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 1,843 ms / 3,000 ms
コード長 8,616 bytes
コンパイル時間 3,149 ms
コンパイル使用メモリ 218,932 KB
実行使用メモリ 16,944 KB
スコア 65,580
最終ジャッジ日時 2023-04-15 11:41:08
合計ジャッジ時間 97,303 ms
ジャッジサーバーID
（参考情報） 		judge12 / judge11
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1,136 ms
15,968 KB
testcase_01 AC 1,060 ms
15,712 KB
testcase_02 AC 823 ms
15,588 KB
testcase_03 AC 675 ms
15,224 KB
testcase_04 AC 1,229 ms
16,016 KB
testcase_05 AC 352 ms
15,712 KB
testcase_06 AC 1,247 ms
16,620 KB
testcase_07 AC 765 ms
16,500 KB
testcase_08 AC 881 ms
16,644 KB
testcase_09 AC 677 ms
15,960 KB
testcase_10 AC 652 ms
15,964 KB
testcase_11 AC 411 ms
15,648 KB
testcase_12 AC 722 ms
15,916 KB
testcase_13 AC 755 ms
15,848 KB
testcase_14 AC 1,030 ms
15,440 KB
testcase_15 AC 691 ms
15,640 KB
testcase_16 AC 787 ms
15,528 KB
testcase_17 AC 722 ms
16,556 KB
testcase_18 AC 497 ms
16,376 KB
testcase_19 AC 965 ms
16,288 KB
testcase_20 AC 734 ms
16,276 KB
testcase_21 AC 906 ms
16,080 KB
testcase_22 AC 491 ms
15,708 KB
testcase_23 AC 1,250 ms
15,816 KB
testcase_24 AC 932 ms
16,076 KB
testcase_25 AC 917 ms
16,240 KB
testcase_26 AC 810 ms
15,888 KB
testcase_27 AC 1,057 ms
16,560 KB
testcase_28 AC 994 ms
15,904 KB
testcase_29 AC 775 ms
15,692 KB
testcase_30 AC 484 ms
16,228 KB
testcase_31 AC 1,175 ms
16,232 KB
testcase_32 AC 1,062 ms
15,700 KB
testcase_33 AC 941 ms
15,900 KB
testcase_34 AC 739 ms
16,008 KB
testcase_35 AC 779 ms
15,368 KB
testcase_36 AC 1,003 ms
15,960 KB
testcase_37 AC 940 ms
15,640 KB
testcase_38 AC 1,023 ms
15,904 KB
testcase_39 AC 712 ms
16,492 KB
testcase_40 AC 441 ms
16,160 KB
testcase_41 AC 1,544 ms
16,580 KB
testcase_42 AC 994 ms
16,940 KB
testcase_43 AC 984 ms
16,116 KB
testcase_44 AC 902 ms
15,504 KB
testcase_45 AC 1,666 ms
16,416 KB
testcase_46 AC 572 ms
16,620 KB
testcase_47 AC 944 ms
15,428 KB
testcase_48 AC 1,092 ms
16,168 KB
testcase_49 AC 837 ms
16,236 KB
testcase_50 AC 784 ms
15,620 KB
testcase_51 AC 1,229 ms
15,760 KB
testcase_52 AC 1,180 ms
16,944 KB
testcase_53 AC 895 ms
16,236 KB
testcase_54 AC 708 ms
16,168 KB
testcase_55 AC 1,594 ms
16,284 KB
testcase_56 AC 771 ms
15,552 KB
testcase_57 AC 964 ms
15,496 KB
testcase_58 AC 1,191 ms
16,220 KB
testcase_59 AC 748 ms
16,116 KB
testcase_60 AC 552 ms
15,564 KB
testcase_61 AC 630 ms
15,112 KB
testcase_62 AC 1,142 ms
16,684 KB
testcase_63 AC 609 ms
16,548 KB
testcase_64 AC 1,026 ms
16,296 KB
testcase_65 AC 711 ms
15,740 KB
testcase_66 AC 903 ms
16,492 KB
testcase_67 AC 577 ms
16,520 KB
testcase_68 AC 1,843 ms
16,080 KB
testcase_69 AC 564 ms
15,608 KB
testcase_70 AC 922 ms
16,488 KB
testcase_71 AC 680 ms
16,224 KB
testcase_72 AC 1,046 ms
16,668 KB
testcase_73 AC 513 ms
16,048 KB
testcase_74 AC 1,028 ms
15,628 KB
testcase_75 AC 754 ms
15,824 KB
testcase_76 AC 1,015 ms
16,176 KB
testcase_77 AC 891 ms
15,624 KB
testcase_78 AC 768 ms
16,348 KB
testcase_79 AC 655 ms
15,700 KB
testcase_80 AC 821 ms
15,552 KB
testcase_81 AC 1,049 ms
16,012 KB
testcase_82 AC 328 ms
14,848 KB
testcase_83 AC 499 ms
16,432 KB
testcase_84 AC 718 ms
15,588 KB
testcase_85 AC 873 ms
15,324 KB
testcase_86 AC 516 ms
16,544 KB
testcase_87 AC 931 ms
16,804 KB
testcase_88 AC 326 ms
14,496 KB
testcase_89 AC 848 ms
15,588 KB
testcase_90 AC 869 ms
15,700 KB
testcase_91 AC 998 ms
16,764 KB
testcase_92 AC 1,115 ms
16,284 KB
testcase_93 AC 1,029 ms
16,276 KB
testcase_94 AC 570 ms
16,304 KB
testcase_95 AC 835 ms
15,484 KB
testcase_96 AC 1,311 ms
16,052 KB
testcase_97 AC 414 ms
14,640 KB
testcase_98 AC 933 ms
16,284 KB
testcase_99 AC 873 ms
16,008 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#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> 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[64 * ky + kx] + distance_key[64 * y + x];
        }
        res -= block;
        res *= 10 * D;
        res += param * score + hp;
        return res;
    }

    // action: 0 to 12
    // return: is_legal
    bool advance(const int action) {
        turn++;
        const int d = action & 3;
        int ny = y + dy[d], nx = x + dx[d];
        if (action < 4) {  // move
            if (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) {  // block
            if (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) {  // fire
            if (fire == 0) return false;
            while (not range_out(ny, nx)) {
                int state = board[64 * ny + nx];
                if (2 <= state and state <= 5) {  // enemy
                    board[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) {  // enemy
                    if (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] = 0;
    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();
    }

    param = 0;
    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;
}
0