#860312 (C++11) No.5015 Escape from Labyrinth

提出ソース

結果

問題	No.5015 Escape from Labyrinth
ユーザー	a9ua1i0n
提出日時	2023-04-16 19:07:25
言語	C++11 (gcc 11.4.0)
結果	AC
実行時間	2,622 ms / 3,000 ms
コード長	10,443 bytes
コンパイル時間	2,958 ms
コンパイル使用メモリ	197,996 KB
実行使用メモリ	98,928 KB
スコア	13,760
最終ジャッジ日時	2023-04-16 19:11:55
合計ジャッジ時間	269,851 ms
ジャッジサーバーID （参考情報）	judge12 / judge16
	純コード判定しない問題か言語

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2,582 ms 55,796 KB
testcase_01	AC	2,597 ms 75,308 KB
testcase_02	AC	2,590 ms 91,092 KB
testcase_03	AC	2,590 ms 71,208 KB
testcase_04	AC	2,606 ms 78,660 KB
testcase_05	AC	2,598 ms 64,244 KB
testcase_06	AC	2,598 ms 95,292 KB
testcase_07	AC	2,606 ms 77,732 KB
testcase_08	AC	2,582 ms 75,200 KB
testcase_09	AC	2,558 ms 58,896 KB
testcase_10	AC	2,585 ms 81,628 KB
testcase_11	AC	2,564 ms 75,896 KB
testcase_12	AC	2,569 ms 64,220 KB
testcase_13	AC	2,599 ms 75,740 KB
testcase_14	AC	2,577 ms 63,572 KB
testcase_15	AC	2,591 ms 95,912 KB
testcase_16	AC	2,613 ms 68,012 KB
testcase_17	AC	2,622 ms 79,756 KB
testcase_18	AC	2,593 ms 97,524 KB
testcase_19	AC	2,600 ms 86,688 KB
testcase_20	AC	2,600 ms 70,144 KB
testcase_21	AC	2,573 ms 85,108 KB
testcase_22	AC	2,592 ms 64,400 KB
testcase_23	AC	2,570 ms 72,940 KB
testcase_24	AC	2,575 ms 82,340 KB
testcase_25	AC	2,576 ms 91,020 KB
testcase_26	AC	2,558 ms 75,656 KB
testcase_27	AC	2,582 ms 71,240 KB
testcase_28	AC	2,557 ms 84,048 KB
testcase_29	AC	2,580 ms 87,480 KB
testcase_30	AC	2,582 ms 79,780 KB
testcase_31	AC	2,573 ms 85,444 KB
testcase_32	AC	2,593 ms 82,452 KB
testcase_33	AC	2,565 ms 66,856 KB
testcase_34	AC	2,564 ms 86,652 KB
testcase_35	AC	2,603 ms 86,240 KB
testcase_36	AC	2,559 ms 70,372 KB
testcase_37	AC	2,580 ms 79,068 KB
testcase_38	AC	2,585 ms 81,464 KB
testcase_39	AC	2,589 ms 73,156 KB
testcase_40	AC	2,588 ms 62,728 KB
testcase_41	AC	2,588 ms 72,032 KB
testcase_42	AC	2,564 ms 79,088 KB
testcase_43	AC	2,570 ms 91,648 KB
testcase_44	AC	2,586 ms 71,848 KB
testcase_45	AC	2,569 ms 55,480 KB
testcase_46	AC	2,559 ms 72,164 KB
testcase_47	AC	2,564 ms 87,048 KB
testcase_48	AC	2,591 ms 63,444 KB
testcase_49	AC	2,558 ms 67,140 KB
testcase_50	AC	2,583 ms 71,792 KB
testcase_51	AC	2,593 ms 71,064 KB
testcase_52	AC	2,583 ms 82,232 KB
testcase_53	AC	2,564 ms 79,092 KB
testcase_54	AC	2,593 ms 72,904 KB
testcase_55	AC	2,559 ms 77,388 KB
testcase_56	AC	2,578 ms 79,400 KB
testcase_57	AC	2,609 ms 70,196 KB
testcase_58	AC	2,570 ms 70,248 KB
testcase_59	AC	2,570 ms 70,652 KB
testcase_60	AC	2,616 ms 79,712 KB
testcase_61	AC	2,573 ms 58,704 KB
testcase_62	AC	2,576 ms 63,084 KB
testcase_63	AC	2,589 ms 58,024 KB
testcase_64	AC	2,568 ms 72,180 KB
testcase_65	AC	2,569 ms 68,720 KB
testcase_66	AC	2,586 ms 55,376 KB
testcase_67	AC	2,562 ms 69,268 KB
testcase_68	AC	2,562 ms 76,104 KB
testcase_69	AC	2,561 ms 78,436 KB
testcase_70	AC	2,599 ms 98,928 KB
testcase_71	AC	2,577 ms 67,288 KB
testcase_72	AC	2,574 ms 86,728 KB
testcase_73	AC	2,584 ms 94,868 KB
testcase_74	AC	2,563 ms 77,296 KB
testcase_75	AC	2,565 ms 81,496 KB
testcase_76	AC	2,602 ms 90,468 KB
testcase_77	AC	2,562 ms 58,592 KB
testcase_78	AC	2,567 ms 64,832 KB
testcase_79	AC	2,585 ms 68,984 KB
testcase_80	AC	2,564 ms 79,568 KB
testcase_81	AC	2,573 ms 77,168 KB
testcase_82	AC	2,569 ms 75,384 KB
testcase_83	AC	2,566 ms 70,500 KB
testcase_84	AC	2,579 ms 94,072 KB
testcase_85	AC	2,554 ms 64,588 KB
testcase_86	AC	2,616 ms 73,768 KB
testcase_87	AC	2,556 ms 75,368 KB
testcase_88	AC	2,569 ms 86,672 KB
testcase_89	AC	2,589 ms 84,976 KB
testcase_90	AC	2,568 ms 78,492 KB
testcase_91	AC	2,574 ms 73,048 KB
testcase_92	AC	2,592 ms 70,388 KB
testcase_93	AC	2,571 ms 73,168 KB
testcase_94	AC	2,585 ms 72,732 KB
testcase_95	AC	2,600 ms 93,796 KB
testcase_96	AC	2,577 ms 50,948 KB
testcase_97	AC	2,570 ms 56,808 KB
testcase_98	AC	2,589 ms 76,380 KB
testcase_99	AC	2,585 ms 74,904 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

#include <bits/stdc++.h>

using namespace std;

const int grid_size = 60; // 迷宮の大きさ
const int max_hp = 1500;  // 初期体力
int dy[4] = {-1, 1, 0, 0};
int dx[4] = {0, 0, -1, 1};
string dir = "UDLR";

// 探知機の情報
struct enemy {
    int y, x, d, num;
    bool destroyed;
    enemy(int y, int x, int d, int num) {
        this->y = y, this->x = x, this->d = d;
        this->num = num;
        destroyed = false;
    }
};

// 範囲外かどうか
bool range_out(int y, int x) {
    if (y < 0 || y >= grid_size)
        return true;
    if (x < 0 || x >= grid_size)
        return true;
    return false;
}

class action {
  public:
    virtual void print() = 0;
};

// class pause: public action {
//   public:
//     void print() override {
//         cout << "S"
//              << "\n";
//     }
// };
class transfer: public action {
    char dir;

  public:
    transfer(char dir):
        dir(dir) {}

    void print() {
        cout << "M " << this->dir
             << "\n";
    }
};
// class fire: public action {
//     char dir;

//   public:
//     fire(char dir):
//         dir(dir) {}
//     void print() override {
//         cout << "F " << this->dir
//              << "\n";
//     }
// };
// BFSによる経路探索
vector<transfer> find_path(int sy, int sx, int gy, int gx, vector<string>& S) {
    int siz = S.size();
    vector<vector<int>> dist(siz, vector<int>(siz, -1));
    dist[sy][sx] = 0;
    queue<pair<int, int>> q;
    q.emplace(sy, sx);
    while (!q.empty()) {
        pair<int, int> p = q.front();
        q.pop();
        int y = p.first, x = p.second;
        for (int k = 0; k < 4; k++) {
            int ny = y + dy[k], nx = x + dx[k];
            if (range_out(ny, nx))
                continue;
            if (dist[ny][nx] != -1)
                continue;
            char cell = S[ny][nx];
            if (cell == '#' || cell == 'B' || cell == 'E')
                continue;
            dist[ny][nx] = dist[y][x] + 1;
            q.emplace(ny, nx);
        }
    }
    vector<transfer> res;
    if (dist[gy][gx] == -1)
        return res;
    int now_y = gy, now_x = gx, now_d = dist[gy][gx];
    while (now_y != sy || now_x != sx) {
        bool moved = false;
        for (int k = 0; k < 4; k++) {
            int new_y = now_y + dy[k], new_x = now_x + dx[k];
            if (range_out(new_y, new_x))
                continue;
            if (dist[new_y][new_x] != now_d - 1)
                continue;
            now_y = new_y, now_x = new_x;
            now_d--;
            res.push_back(transfer(dir[k ^ 1]));
            moved = true;
            break;
        }
        assert(moved);
    }
    reverse(res.begin(), res.end());
    return res;
}

pair<int, int> start_yx;
pair<int, int> goal_yx;
pair<int, int> key_yx;
int dist(pair<int, int> pos, int y, int x) {
    return abs(pos.first - y) + abs(pos.second - x);
}
class board {
  public:
    vector<transfer> ans;
    bitset<500> gem;
    int hp = 1500;
    int powder = 0;
    int y = 0;
    int x = 0;
    bool has_key = false;
    board(int y, int x):
        y(y), x(x) {}
    board(int y, int x, vector<transfer>& ans, bitset<500> gem, int hp, int powder, bool has_key):
        y(y), x(x), ans(ans), gem(gem), hp(hp), powder(powder), has_key(has_key) {}
};
int get_score(const board& b) {
    int score = 0;
    score += b.gem.count() * 10;

    // score += b.hp;
    if (b.has_key)
        score += (grid_size * 2 - dist(goal_yx, b.y, b.x)) * 10;
    else
        score += grid_size * 2 - dist(key_yx, b.y, b.x);

    // if (b.has_key)
    //     score *= 10;
    return score;
}
bool operator<(const board& t1, const board& t2) {
    return get_score(t1) < get_score(t2);
};
bool operator>(const board& t1, const board& t2) {
    return t2 < t1;
}
bool operator<=(const board& t1, const board& t2) {
    return !(t1 > t2);
}
bool operator>=(const board& t1, const board& t2) {
    return !(t1 < t2);
}

int check_damages(vector<vector<set<int>>>& is_detectedable, vector<enemy>& E, int y, int x, int turn) {
    int damages = 0;
    for (auto itr = is_detectedable[y][x].begin(); itr != is_detectedable[y][x].begin(); itr++) {
        if (turn % E[*itr].d == 0) {
            damages++;
        }
    }
    return damages;
}
void wrapper(action& act) {
    act.print();
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    auto start = clock();

    // 入力の受け取り
    int N, D, H;
    cin >> N >> D >> H;
    vector<string> S(N);
    for (int i = 0; i < N; i++)
        cin >> S[i];
    int M;
    cin >> M;
    vector<enemy> E;
    for (int i = 0; i < M; i++) {
        int y, x, d;
        cin >> y >> x >> d;
        E.emplace_back(y, x, d, i);
    }

    vector<vector<set<int>>> is_detectedable(N, vector<set<int>>(N));
    for (int i = 0; i < M; i++) {
        for (int d = 0; d < 4; d++) {
            int y = E[i].y + dy[d];
            int x = E[i].x + dx[d];
            while (!range_out(y, x)) {
                if (S[y][x] == '#' || S[y][x] == 'E') {
                    break;
                }
                is_detectedable[y][x].insert(i);
                y += dy[d];
                x += dx[d];
            }
        }
    }

    map<int, map<int, int>> gems;
    map<int, map<int, int>> powders;
    {
        int g = 0;
        int p = 0;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (S[i][j] == 'S') {
                    start_yx = pair<int, int>(i, j);
                }
                if (S[i][j] == 'G') {
                    goal_yx = pair<int, int>(i, j);
                }
                if (S[i][j] == 'K') {
                    key_yx = pair<int, int>(i, j);
                }
                if (S[i][j] == 'J') {
                    gems[i][j] = g;
                    g++;
                }
                if (S[i][j] == 'J') {
                    powders[i][j] = p;
                    p++;
                }
            }
        }
    }

    // beam search
    board best_ans = board(start_yx.first, start_yx.second);

    int beam_width = 5000;

    int it = 0;
    priority_queue<board, vector<board>, less<board>> que, nque;
    que.push(best_ans);

    vector<transfer> find_key = find_path(start_yx.first, start_yx.second, key_yx.first, key_yx.second, S);
    vector<transfer> goal = find_path(key_yx.first, key_yx.second, goal_yx.first, goal_yx.second, S);
    best_ans.ans.insert(best_ans.ans.end(), find_key.begin(), find_key.end());
    best_ans.ans.insert(best_ans.ans.end(), goal.begin(), goal.end());

    while ((clock() - start) < 2.5 * CLOCKS_PER_SEC) {
        // cerr << "queue.top: " << que.top().hp << " " << que.top().gem.count() << " " << boolalpha << que.top().has_key << " " << que.top().x << " " << que.top().y << "  : " << get_score(que.top())
        //      << "\n";
        if (que.empty())
            break;
        it++;
        for (int w = 0; w < beam_width; w++) {
            if (que.empty()) {
                break;
            }
            auto b = que.top();
            que.pop();

            for (int d = 0; d < 4; d++) {
                int ny = b.y + dy[d];
                int nx = b.x + dx[d];
                if (range_out(ny, nx)) {
                    continue;
                }
                bool can_push = true;
                int nhp = b.hp - 1;
                if (nhp <= 0) {
                    continue;
                }
                int npowder = b.powder;
                bitset<500> ngem = b.gem;
                bool key = b.has_key;
                switch (S[ny][nx]) {
                    case '.':
                        nhp -= D * check_damages(is_detectedable, E, ny, nx, b.ans.size() + 1);
                        break;
                    case '#':
                        can_push = false;
                        break;
                    case 'S':
                        nhp -= D * check_damages(is_detectedable, E, ny, nx, b.ans.size() + 1);
                        break;
                    case 'G':
                        if (b.has_key) {
                            // cerr << "ans"
                            //      << "\n";
                            auto nb = board(ny, nx, b.ans, ngem, nhp, npowder, b.has_key);
                            nb.ans.push_back(transfer(dir[d]));
                            if (best_ans < nb) {
                                // cerr << "ans"
                                //      << " " << nb.gem.count()
                                //      << "\n";
                                best_ans = nb;
                            }
                            can_push = false;
                        } else {
                            nhp -= D * check_damages(is_detectedable, E, ny, nx, b.ans.size() + 1);
                        }
                        break;
                    case 'K':
                        nhp -= D * check_damages(is_detectedable, E, ny, nx, b.ans.size() + 1);
                        key = true;
                        break;
                    case 'J':
                        nhp -= D * check_damages(is_detectedable, E, ny, nx, b.ans.size() + 1);
                        ngem[gems[ny][nx]] = true;
                        break;
                    case 'F':
                        nhp -= D * check_damages(is_detectedable, E, ny, nx, b.ans.size() + 1);
                        // TODO: powder取得
                        break;
                    case 'E':
                        can_push = false;
                        break;

                    default:
                        break;
                }
                if (!can_push) {
                    continue;
                }
                if (nhp <= 0) {
                    continue;
                }
                auto nb = board(ny, nx, b.ans, ngem, nhp, npowder, key);
                nb.ans.push_back(transfer(dir[d]));
                nque.push(nb);
            }
            // b.ans.push_back(pause());
            // b.hp--;
            // if (b.hp > 0)
            //     nque.push(b);
        }
        que = nque;
        priority_queue<board, vector<board>, less<board>> e;
        swap(nque, e);
    }
    cerr << "iter: " << it << "\n";
    cerr << "best-ans: " << best_ans.ans.size() << "\n";
    for (auto itr = best_ans.ans.begin(); itr != best_ans.ans.end(); itr++) {
        wrapper(*itr);
    }

    return 0;
}

yukicoder

結果

テストケース

ソースコード