#860312 (C++11（廃止可能性あり）) No.5015 Escape from Labyrinth

• 問題: No.5015 Escape from Labyrinth
• ユーザー: a9ua1i0n
• 提出日時: 2023-04-16 19:07:25
• 言語: C++11（廃止可能性あり） (gcc 13.3.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

ファイルパターン	結果
other	AC * 100

ソースコード

#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;
}