#859889 (C++17) No.5015 Escape from Labyrinth

提出ソース

結果

問題	No.5015 Escape from Labyrinth
ユーザー	👑 platinum
提出日時	2023-04-15 03:32:48
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	WA
実行時間	-
コード長	25,029 bytes
コンパイル時間	5,445 ms
コンパイル使用メモリ	228,144 KB
実行使用メモリ	336,220 KB
スコア	147,000
最終ジャッジ日時	2023-04-15 11:45:41
合計ジャッジ時間	121,646 ms
ジャッジサーバーID （参考情報）	judge11 / judge12

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	1,225 ms 308,556 KB
testcase_01	AC	1,052 ms 222,612 KB
testcase_02	AC	1,001 ms 177,892 KB
testcase_03	AC	987 ms 136,416 KB
testcase_04	AC	928 ms 145,388 KB
testcase_05	AC	1,196 ms 214,076 KB
testcase_06	AC	1,199 ms 267,928 KB
testcase_07	AC	947 ms 163,376 KB
testcase_08	AC	914 ms 141,312 KB
testcase_09	AC	993 ms 148,644 KB
testcase_10	AC	1,087 ms 208,448 KB
testcase_11	AC	1,038 ms 203,052 KB
testcase_12	AC	1,029 ms 191,048 KB
testcase_13	AC	956 ms 147,584 KB
testcase_14	AC	942 ms 129,168 KB
testcase_15	AC	1,303 ms 323,672 KB
testcase_16	AC	1,134 ms 261,044 KB
testcase_17	AC	989 ms 225,720 KB
testcase_18	AC	932 ms 206,920 KB
testcase_19	AC	938 ms 179,996 KB
testcase_20	AC	1,281 ms 297,940 KB
testcase_21	AC	1,223 ms 265,276 KB
testcase_22	AC	1,104 ms 215,308 KB
testcase_23	WA	-
testcase_24	AC	953 ms 150,168 KB
testcase_25	AC	1,053 ms 224,088 KB
testcase_26	AC	1,020 ms 179,460 KB
testcase_27	AC	1,105 ms 192,120 KB
testcase_28	AC	972 ms 211,656 KB
testcase_29	AC	983 ms 194,520 KB
testcase_30	AC	1,286 ms 299,048 KB
testcase_31	AC	1,177 ms 261,956 KB
testcase_32	AC	1,025 ms 172,584 KB
testcase_33	AC	957 ms 133,388 KB
testcase_34	AC	826 ms 149,488 KB
testcase_35	AC	1,289 ms 275,296 KB
testcase_36	AC	1,136 ms 259,660 KB
testcase_37	AC	1,128 ms 245,744 KB
testcase_38	AC	977 ms 149,048 KB
testcase_39	AC	842 ms 169,564 KB
testcase_40	AC	1,070 ms 196,648 KB
testcase_41	AC	1,060 ms 194,724 KB
testcase_42	AC	1,081 ms 250,900 KB
testcase_43	AC	933 ms 192,488 KB
testcase_44	AC	913 ms 150,420 KB
testcase_45	AC	1,303 ms 336,220 KB
testcase_46	AC	1,186 ms 269,228 KB
testcase_47	AC	1,102 ms 227,844 KB
testcase_48	AC	937 ms 156,964 KB
testcase_49	AC	969 ms 139,880 KB
testcase_50	AC	1,208 ms 311,792 KB
testcase_51	AC	1,129 ms 252,316 KB
testcase_52	AC	1,103 ms 227,904 KB
testcase_53	AC	1,032 ms 167,124 KB
testcase_54	AC	1,014 ms 174,092 KB
testcase_55	AC	1,222 ms 304,940 KB
testcase_56	AC	1,164 ms 273,900 KB
testcase_57	AC	1,025 ms 180,796 KB
testcase_58	AC	868 ms 138,668 KB
testcase_59	AC	972 ms 197,424 KB
testcase_60	AC	1,294 ms 313,904 KB
testcase_61	AC	1,145 ms 248,964 KB
testcase_62	AC	1,018 ms 156,676 KB
testcase_63	WA	-
testcase_64	AC	885 ms 141,240 KB
testcase_65	AC	1,296 ms 294,028 KB
testcase_66	AC	1,081 ms 201,312 KB
testcase_67	AC	1,078 ms 213,872 KB
testcase_68	AC	986 ms 215,224 KB
testcase_69	AC	893 ms 173,864 KB
testcase_70	AC	1,210 ms 308,568 KB
testcase_71	AC	1,152 ms 252,308 KB
testcase_72	AC	1,030 ms 187,312 KB
testcase_73	AC	920 ms 135,396 KB
testcase_74	AC	861 ms 133,376 KB
testcase_75	AC	1,127 ms 291,668 KB
testcase_76	AC	952 ms 164,892 KB
testcase_77	AC	980 ms 163,692 KB
testcase_78	AC	1,010 ms 200,140 KB
testcase_79	AC	917 ms 145,808 KB
testcase_80	AC	1,293 ms 306,520 KB
testcase_81	AC	1,191 ms 253,372 KB
testcase_82	AC	1,134 ms 220,976 KB
testcase_83	AC	977 ms 218,220 KB
testcase_84	AC	968 ms 142,492 KB
testcase_85	AC	1,203 ms 216,140 KB
testcase_86	AC	1,120 ms 258,396 KB
testcase_87	AC	1,250 ms 241,972 KB
testcase_88	AC	1,011 ms 218,868 KB
testcase_89	AC	944 ms 184,496 KB
testcase_90	AC	964 ms 189,508 KB
testcase_91	AC	1,155 ms 257,336 KB
testcase_92	AC	945 ms 149,208 KB
testcase_93	AC	1,035 ms 183,968 KB
testcase_94	AC	946 ms 160,176 KB
testcase_95	AC	1,199 ms 299,144 KB
testcase_96	AC	1,174 ms 243,808 KB
testcase_97	AC	1,176 ms 229,352 KB
testcase_98	AC	973 ms 183,824 KB
testcase_99	AC	1,006 ms 175,776 KB

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

ソースコード

raw source code

#include <iostream>
#include <vector>
#include <queue>
#include <string>
#include <sstream>
#include <algorithm>
#include <set>
#include <unordered_map>
#include <random>
#include <cassert>

using namespace std;
using pii = pair<int,int>;

const int grid_size = 60;
const int max_hp = 1500;
const int jewel_value = 10;
int dy[5] = {-1, 1, 0, 0, 0};
int dx[5] = {0, 0, -1, 1, 0};
string dir = "UDLRS";
const int INF = (int)1e9;

const int testcase = 1;

enum class file_status{
    local,
    score,
    submit,
};
file_status now_status = file_status::submit;

void read_input(){
    std::stringstream ss;
    std::string num = std::to_string(testcase);
    int siz = num.size();
    for(int i = 0; i < 3 - siz; i++) num = '0' + num;
    ss << "in/testcase_" << num << ".txt";
    FILE *in = freopen(ss.str().c_str(), "r", stdin);
}
void file_output(){
    std::stringstream ss;
    std::string num = std::to_string(testcase);
    int siz = num.size();
    for(int i = 0; i < 3 - siz; i++) num = '0' + num;
    ss << "test_out/testcase_" << num << ".txt";
    FILE *out = freopen(ss.str().c_str(), "w", stdout);
}

// セルの情報の候補
enum class cell_status{
    empty,
    wall,
    block,
    enemy,
    key,
    goal,
    fire,
    jewel,
    player,
    cell_kinds,
};
int GetCellStatusNumber(cell_status st){
    if(st == cell_status::empty) return 0;
    else if(st == cell_status::wall) return 1;
    else if(st == cell_status::block) return 2;
    else if(st == cell_status::enemy) return 3;
    else if(st == cell_status::key) return 4;
    else if(st == cell_status::goal) return 5;
    else if(st == cell_status::fire) return 6;
    else if(st == cell_status::jewel) return 7;
    else if(st == cell_status::cell_kinds) return 8;
    return -1;
}

// 探知機の情報
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;
    }
};

// セルの情報
struct Cell{
    cell_status status;
    Enemy* e_pointer = nullptr;
    Cell(cell_status st = cell_status::empty) : status(st) {}
};

template<typename T>
struct v2{
    std::vector<std::vector<T>> v;
    v2(){}
    v2(int x){
        v.resize(x);
    }
    v2(int x, int y){
        v.resize(x, std::vector<T>(y));
    }
    v2(int x, int y, T val){
        v.resize(x, std::vector<T>(y, val));
    }
    std::vector<T>& operator [] (const int num){
        return v[num];
    }
    void init(int x){
        v.resize(x);
    }
    void init(int x, int y){
        v.resize(x, std::vector<T>(y));
    }
    void init(int x, int y, T val){
        v.resize(x, std::vector<T>(y, val));
    }
    void push_back(std::vector<T>& e){
        v.emplace_back(e);
    }
    int size(){
        return (int)v.size();
    }
    bool empty(){
        return v.empty();
    }
    void clear(){
        v.clear();
    }
    void erase(int pos){
        v.erase(v.begin() + pos);
    }
};

template<typename T>
struct v3{
    std::vector<v2<T>> v;
    v3(){}
    v3(int x){
        v.resize(x);
    }
    v3(int x, int y){
        v.resize(x, v2<T>(y));
    }
    v3(int x, int y, int z){
        v.resize(x, v2<T>(y, z));
    }
    v3(int x, int y, int z, T val){
        v.resize(x, v2<T>(y, z, val));
    }
    v2<T>& operator [] (const int num){
        return v[num];
    }
    void init(int x, int y){
        v.resize(x, v2<T>(y));
    }
    void init(int x, int y, int z){
        v.resize(x, v2<T>(y, z));
    }
    void push_back(v2<T>& e){
        v.emplace_back(e);
    }
    bool empty(){
        return v.empty();
    }
    void clear(){
        v.clear();
    }
};

// ソートされた配列からの探索
bool is_included(vector<int> &vec, int val){
    int find = upper_bound(vec.begin(), vec.end(), val)
    - lower_bound(vec.begin(), vec.end(), val);
    if(find) return true;
    else return false;
}

random_device rnd;
mt19937 engine(rnd());
vector<long long> hash_list;
void hash_init(){
    uniform_int_distribution<> h(1, (int)1e9);
    int kinds_num = GetCellStatusNumber(cell_status::cell_kinds);
    for(int i = 0; i < grid_size * grid_size * kinds_num; i++){
        long long val1 = h(engine);
        long long val2 = h(engine);
        hash_list.emplace_back(val1 * val2);
    }
}
long long get_hash(int y, int x, cell_status st){
    int kinds_num = GetCellStatusNumber(cell_status::cell_kinds);
    int num = (y * grid_size + x) * kinds_num + GetCellStatusNumber(st);
    return hash_list[num];
}
long long zobrist_hash(v2<Cell>& now_grid){
    long long res = 0;
    for(int i = 0; i < grid_size; i++){
        for(int j = 0; j < grid_size; j++){
            res ^= get_hash(i, j, now_grid[i][j].status);
        }
    }
    return res;
}
long long hash_update(int ny, int nx, v2<Cell>& now_grid){
    long long res = 0;
    long long o = get_hash(ny, nx, now_grid[ny][nx].status);
    long long n = get_hash(ny, nx, cell_status::empty);
    res = o ^ n;
    return res;
}
unordered_map<long long, v2<Cell>> Grids;

// ダイクストラ法で用いる情報
struct pathway{
    int dist;
    int y, x, t;
    long long hash;
    pathway(int d, int y, int x, int t, long long h) :
    dist(d), y(y), x(x), t(t), hash(h) {}
    bool operator> (const pathway& p) const{
        return dist > p.dist;
    }
};

int N, D, H, M;
vector<Enemy> enemy;
vector<string> S;
v2<Cell> grid;

int sy, sx, ky, kx, gy, gx;

v2<int> enemy_number;
v2<int> jewel_number;
vector<pii> jewel_pos;
v2<int> fire_number;
vector<pii> fire_pos;

// 範囲外かどうか
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;
}

// プレイヤーの情報
struct Player{
    int y, x;
    int hp, fire;
    int score;
    bool get_key, using_magic;
    Player() {}
    Player(int y, int x) : y(y), x(x){
        hp = max_hp;
        fire = 0;
        score = 0;
        get_key = false;
        using_magic = false;
    }
    int move(int k){
        int ny = y + dy[k], nx = x + dx[k];
        if(range_out(ny, nx)) return -1;
        if(grid[ny][nx].status == cell_status::wall
        || grid[ny][nx].status == cell_status::block
        || grid[ny][nx].status == cell_status::enemy){
            return -1;
        }
        if(grid[ny][nx].status == cell_status::fire){
            fire++;
        }
        else if(grid[ny][nx].status == cell_status::jewel){
            score += jewel_value;
        }
        else if(grid[ny][nx].status == cell_status::key){
            get_key = true;
        }
        y = ny; x = nx;
        return 0;
    }
    void damage(int d){
        hp -= d;
    }
};

// 方向を取得
int get_direction(char d){
    for(int k = 0; k < 4; k++){
        if(d == dir[k]) return k;
    }
    return -1;
}

void input(){
    cin >> N >> D >> H;

    S.resize(N);
    for(int i = 0; i < N; i++) cin >> S[i];
    enemy_number.init(N, N, -1);
    jewel_number.init(N, N, -1);
    fire_number.init(N, N, -1);

    cin >> M;
    for(int i = 0; i < M; i++){
        int y, x, d;
        cin >> y >> x >> d;
        enemy.emplace_back(y, x, d, i);
        enemy_number[y][x] = i;
    }

    grid.init(N, N, cell_status::empty);
    for(int i = 0; i < N; i++){
        for(int j = 0; j < N; j++){
            if(S[i][j] == '#'){
                grid[i][j].status = cell_status::wall;
            }
            else if(S[i][j] == 'E'){
                grid[i][j].status = cell_status::enemy;
                grid[i][j].e_pointer = &enemy[enemy_number[i][j]];
            }
            else if(S[i][j] == 'K'){
                grid[i][j].status = cell_status::key;
            }
            else if(S[i][j] == 'G'){
                grid[i][j].status = cell_status::goal;
            }
            else if(S[i][j] == 'F'){
                grid[i][j].status = cell_status::fire;
                fire_number[i][j] = (int)fire_pos.size();
                fire_pos.emplace_back(i, j);
            }
            else if(S[i][j] == 'J'){
                grid[i][j].status = cell_status::jewel;
                jewel_number[i][j] = (int)jewel_pos.size();
                jewel_pos.emplace_back(i, j);
            }
            else if(S[i][j] == 'S'){
                grid[i][j].status = cell_status::player;
            }
            else{
                grid[i][j].status = cell_status::empty;
            }
        }
    }
}

uniform_int_distribution<> rand_eval(-5, 5);
struct node{
    Player player;
    int now_turn;
    int eval;
    vector<string> actions;
    // 盤面の記録
    set<int> block_pos; //座標
    vector<int> picked_jewel; //番号
    vector<int> picked_fire; //番号
    vector<int> enemy_destroyed; //番号

    node(Player player){
        this->player = player;
        now_turn = 0;
        eval = 0;
    }
    bool operator< (const node& v) const{
        return eval < v.eval;
    }
};
int get_last_move(node &v){
    if(v.actions.empty() || v.actions.back() == "S") return -1;
    else{
        if(v.actions.back().at(0) != 'M') return -1;
        else return get_direction(v.actions.back().at(2));
    }
}
void update_eval(node &v){
    v.eval = v.player.score;
    v.eval -= (max_hp - v.player.hp) * 0.1 * (1 - v.player.get_key);
    v.eval += rand_eval(engine);
}
void update_actions(node& v, string& query){
    v.now_turn++;
    v.actions.emplace_back(query);
    char c = query[0];
    if(c == 'S') return;
    int k = get_direction(query[2]);
    if(c == 'M'){
        int y = v.player.y + dy[k];
        int x = v.player.x + dx[k];
        cell_status st = grid[y][x].status;
        if(st == cell_status::jewel){
            int j_num = jewel_number[y][x];
            for(auto &num : v.picked_jewel){
                if(j_num == num) return;
            }
            v.picked_jewel.emplace_back(j_num);
            v.player.score += jewel_value;
        }
        else if(st == cell_status::fire){
            int f_num = fire_number[y][x];
            for(auto &num : v.picked_fire){
                if(f_num == num) return;
            }
            v.picked_fire.emplace_back(f_num);
            v.player.fire++;
        }
        else if(st == cell_status::key){
            v.player.get_key = true;
        }
    }
    else if(c == 'B'){
        int y = v.player.y + dy[k];
        int x = v.player.x + dx[k];
        auto itr = v.block_pos.find(y * grid_size + x);
        if(itr == v.block_pos.end()){
            v.block_pos.insert(y * grid_size + x);
        }
        else{
            v.block_pos.erase(itr);
        }
    }
    else if(c == 'F'){
        assert(v.player.fire > 0);
        v.player.fire--;
        int y = v.player.y + dy[k];
        int x = v.player.x + dx[k];
        while(!range_out(y, x)){
            if(grid[y][x].status == cell_status::wall){
                break;
            }
            else if(grid[y][x].status == cell_status::enemy){
                int e_num = enemy_number[y][x];
                bool destroyed = false;
                for(auto &num : v.enemy_destroyed){
                    if(e_num == num){
                        destroyed = true;
                        break;
                    }
                }
                if(destroyed) continue;
                else{
                    v.enemy_destroyed.emplace_back(e_num);
                    break;
                }
            }
            else{
                auto itr = v.block_pos.find(y * grid_size + x);
                if(itr == v.block_pos.end()) continue;
                else break;
            }
        }
    }
}

// プレイヤーへのダメージ計算
int CalcDamage(node& v){
    int res = 1;
    for(int k = 0; k < 4; k++){
        int y = v.player.y + dy[k], x = v.player.x + dx[k];
        while(!range_out(y, x)){
            if(grid[y][x].status == cell_status::wall){
                break;
            }
            else if(grid[y][x].status == cell_status::enemy){
                int e_num = enemy_number[y][x];
                bool destroyed = false;
                for(auto &num : v.enemy_destroyed){
                    if(e_num == num){
                        destroyed = true;
                        break;
                    }
                }
                if(!destroyed){
                    if(v.now_turn % grid[y][x].e_pointer->d == 0){
                        res += D;
                    }
                    break;
                }
            }
            else{
                if(v.block_pos.find(y * grid_size * x) != v.block_pos.end()){
                    break;
                }
            }
            y += dy[k]; x += dx[k];
        }
    }
    return res;
}
int CalcDamage(int py, int px, int t, v2<Cell>& now_grid){
    int res = 1;
    for(int k = 0; k < 4; k++){
        int y = py + dy[k], x = px + dx[k];
        while(!range_out(y, x)){
            if(now_grid[y][x].status == cell_status::wall){
                break;
            }
            if(now_grid[y][x].status == cell_status::block){
                break;
            }
            if(now_grid[y][x].status == cell_status::enemy){
                if(t > 0 && t % now_grid[y][x].e_pointer->d == 0){
                    res += D;
                }
                break;
            }
            y += dy[k]; x += dx[k];
        }
    }
    return res;
}

vector<pii> FindTarget(node& v, int number = 5){
    vector<pii> targets;
    int py = v.player.y, px = v.player.x;

    // 近くにあれば鍵を取りに行く
    int dist_key = abs(py - ky) + abs(px - kx);
    if(!v.player.get_key && dist_key <= 20){
        targets.emplace_back(ky, kx);
        return targets;
    }

    // number個になるまで宝石か火薬を探す
    vector<pii> jewel_fire_list; // first = マンハッタン距離, second = 座標
    vector<int> J = v.picked_jewel;
    vector<int> F = v.picked_fire;
    sort(J.begin(), J.end());
    sort(F.begin(), F.end());

    for(int i = 0; i < (int)jewel_pos.size(); i++){
        if(is_included(J, i)) continue;
        int jy = jewel_pos[i].first, jx = jewel_pos[i].second;
        int dist = abs(py - jy) + abs(px - jx);
        jewel_fire_list.emplace_back(dist, jy * grid_size + jx);
    }
    for(int i = 0; i < (int)fire_pos.size(); i++){
        if(is_included(F, i)) continue;
        int fy = fire_pos[i].first, fx = fire_pos[i].second;
        int dist = abs(py - fy) + abs(px - fx);
        jewel_fire_list.emplace_back(dist, fy * grid_size + fx);
    }
    sort(jewel_fire_list.begin(), jewel_fire_list.end());
    for(int i = 0; i < number; i++){
        int pos = jewel_fire_list[i].second;
        targets.emplace_back(pos / grid_size, pos % grid_size);
    }

    return targets;
}

vector<string> FindPath(node& v, pii& target_pos){
    int py = v.player.y, px = v.player.x;
    int ty = target_pos.first, tx = target_pos.second;
	/*
    // 探索範囲を限定する
    int min_y = min(py, ty) - 1, max_y = max(py, ty) + 1;
    int min_x = min(px, tx) - 1, max_x = max(px, tx) + 1;
    if(min_y < 0) min_y = 0;
    if(min_x < 0) min_x = 0;
    if(max_y >= grid_size) max_y = grid_size - 1;
    if(max_x >= grid_size) max_x = grid_size - 1;
    int wy = max_y - min_y + 1, wx = max_x - min_x + 1;
	*/
	int min_y = 0, min_x = 0;
	int max_y = grid_size - 1, max_x = grid_size - 1;

    v2<int> dist(N, N, -1);
    dist[py-min_y][px-min_x] = 0;
    queue<int> q;
    q.emplace(py * grid_size + px);
    while(!q.empty()){
        if(dist[ty-min_y][tx-min_x] != -1) break;
        int pos = q.front(); q.pop();
        int y = pos / grid_size, x = pos % grid_size;
        for(int k = 0; k < 4; k++){
            int ny = y + dy[k], nx = x + dx[k];
            if(ny < min_y || nx < min_x) continue;
            if(ny > max_y || nx > max_x) continue;
            if(dist[ny-min_y][nx-min_x] != -1) continue;
            cell_status cell = grid[ny][nx].status;
            if(cell == cell_status::wall){
                continue;
            }
            else if(cell == cell_status::enemy){
                bool destroyed = false;
                int e_num = enemy_number[ny][nx];
                for(auto &num : v.enemy_destroyed){
                    if(e_num == num){
                        destroyed = true;
                        break;
                    }
                }
                if(!destroyed) continue;
            }
            else{
                auto itr = v.block_pos.find(ny * grid_size + nx);
                if(itr != v.block_pos.end()) continue;
            }
            dist[ny-min_y][nx-min_x] = dist[y-min_y][x-min_x] + 1;
            q.emplace(ny * grid_size + nx);
        }
    }
    // 経路復元
    vector<string> res;
    if(dist[ty-min_y][tx-min_x] == -1) return res;
    int now_y = ty, now_x = tx, now_d = dist[ty-min_y][tx-min_x];
    while(now_y != py || now_x != px){
        bool moved = false;
        for(int k = 0; k < 4; k++){
            int new_y = now_y + dy[k], new_x = now_x + dx[k];
            if(new_y < min_y || new_x < min_x) continue;
            if(new_y > max_y || new_x > max_x) continue;
            if(dist[new_y-min_y][new_x-min_x] != now_d - 1) continue;
            now_y = new_y, now_x = new_x;
            now_d--;
            string query = "M ";
            query += dir[k^1];
            res.push_back(query);
            moved = true;
            break;
        }
        assert(moved);
    }
    reverse(res.begin(), res.end());
    return res;
}

// ゴールまでの最小の体力減少値をダイクストラ法で見積もる
pair<int,vector<string>> CalcMinDistance(node& v, pii start, pii goal, bool debug = false){
    pair<int,vector<string>> res;

    // 最小公倍数 = 60 倍の頂点を用意する
    const int lcm = 60;
    int start_t = v.now_turn % lcm;
    v3<int> dist(N, N, lcm, INF);
    v3<string> prev_dir(N, N, lcm, "S");
    int start_y = start.first, start_x = start.second;
    int goal_y = goal.first, goal_x = goal.second;
    dist[start_y][start_x][start_t] = 0;
    priority_queue<pathway,vector<pathway>,greater<pathway>> pq;

    // 初期盤面を復元(破壊した探知機と生成したブロック)
    v2<Cell> init_grid = grid;
    for(auto &e_num : v.enemy_destroyed){
        Enemy e = enemy[e_num];
        init_grid[e.y][e.x].status = cell_status::empty;
    }
    for(auto b_num : v.block_pos){
        init_grid[b_num/grid_size][b_num%grid_size] = cell_status::block;
    }

    // 初期盤面をハッシュ化しておく
    long long init_hash = zobrist_hash(init_grid);
    Grids[init_hash] = init_grid;
    pq.emplace(0, start_y, start_x, start_t, init_hash);

    while(!pq.empty()){
        pathway pos = pq.top(); pq.pop();
        int d = pos.dist;
        int y = pos.y;
        int x = pos.x;
        if(y == goal_y && x == goal_x) continue;
        int t = pos.t;
        if(d != dist[y][x][t]) continue;
        // 上下左右への移動またはその場にとどまる
        for(int k = 0; k < 5; k++){
            int ny = y + dy[k], nx = x + dx[k];
            if(range_out(ny, nx)) continue;
            cell_status stat = Grids[pos.hash][ny][nx].status;
            if(stat == cell_status::enemy || stat == cell_status::wall){
                continue;
            }
            // ブロックを破壊する場合
            if(stat == cell_status::block && k < 4){
                v2<Cell> now_grid = Grids[pos.hash];
                long long change = hash_update(ny, nx, Grids[pos.hash]);
                long long new_hash = pos.hash ^ change;
                now_grid[ny][nx].status = cell_status::empty;

                int damage = CalcDamage(y, x, t + 1, now_grid)
                + CalcDamage(ny, nx, t + 2, now_grid);
                int nd = d + damage;
                int nt = (t + 2) % lcm;
                if(nd >= dist[ny][nx][nt]) continue;
                dist[ny][nx][nt] = nd;
                prev_dir[ny][nx][nt] = dir[k];
                prev_dir[ny][nx][nt].push_back(dir[k]);

                Grids[new_hash] = now_grid;
                pq.emplace(nd, ny, nx, nt, new_hash);
            }
            // 単に移動する場合
            else{
                int damage = CalcDamage(ny, nx, t + 1, Grids[pos.hash]);
                int nd = d + damage;
                int nt = (t + 1) % lcm;
                if(nd >= dist[ny][nx][nt]) continue;
                dist[ny][nx][nt] = nd;
                prev_dir[ny][nx][nt] = dir[k];
                pq.emplace(nd, ny, nx, nt, pos.hash);
            }
        }
    }

    int dist_min = INF, goal_t = -1;
    for(int t = 0; t < lcm; t++){
        int dist_t = dist[goal_y][goal_x][t];
        if(dist_min > dist_t){
            dist_min = dist_t;
            goal_t = t;
        }
    }
    res.first = dist_min;
    assert(goal_t != -1);

    // 経路復元
    vector<string> queries;
    int now_y = goal_y, now_x = goal_x, now_t = goal_t;
    if(debug) cout << "#debug start" << endl;
    while(now_y != start_y || now_x != start_x || now_t != start_t){
        if(debug){
            cout << "#t = " << now_t << endl;
            cout << "#(" << now_y  << ", " << now_x << ")" << endl;
            cout << "#d = " << dist[now_y][now_x][now_t] << endl;
        }
        char c = prev_dir[now_y][now_x][now_t][0];
        string query = "M ";
        if(c == 'S') query = c;
        else query += c;
        queries.push_back(query);
        int k = -1;
        if(c == 'S') k = 4;
        else{
            k = get_direction(c);
            k ^= 1;
        }
        // ブロックを破壊した場合
        if(prev_dir[now_y][now_x][now_t].size() > 1){
            c = prev_dir[now_y][now_x][now_t][1];
            string query = "B ";
            query += c;
            queries.push_back(query);
            now_t = (now_t - 1 + lcm) % lcm;
        }
        now_y += dy[k]; now_x += dx[k];
        now_t = (now_t - 1 + lcm) % lcm;
    }

    // デバッグ用の出力
    if(debug){
        cout << "#t = " << now_t << endl;
        cout << "#(" << now_y  << ", " << now_x << ")" << endl;
        cout << "#d = " << dist[now_y][now_x][now_t] << endl;
    }
    if(debug) cout << "#debug end" << endl;

    reverse(queries.begin(), queries.end());
    res.second = queries;
    return res;
}

node BeamSearch(node& init_node){
    node best_node = init_node;
    int best_eval = -INF;
    vector<priority_queue<node>> pq(max_hp);
    pq[0].emplace(init_node);
    const int beam_width = 5;
    
    for(int i = 0; i < max_hp; i++){
        for(int j = 0; j < beam_width; j++){
            if(pq[i].empty()) break;
            node v = pq[i].top(); pq[i].pop();
            
            if(v.player.hp < 500 && !v.player.get_key){
                continue;
            }
            // 余裕をもって打ち切り
            if(v.player.hp < 200 + D * 20){
                continue;
            }
            
            vector<pii> target = FindTarget(v);
            for(auto &pos : target){
                node nv = v;
                vector<string> path = FindPath(nv, pos);
                for(auto &query : path){
                    update_actions(nv, query);
                    if(query[0] == 'M'){
                        int k = get_direction(query[2]);
                        nv.player.move(k);
                    }
                    int d = CalcDamage(nv);
                    nv.player.damage(d);
                }

                // 最高評価なら更新
                update_eval(nv);
                if(nv.eval > best_eval){
                    best_eval = nv.eval;
                    best_node = nv;
                }

                int h = max_hp - nv.player.hp;
                pq[h].emplace(nv);
            }
        }
    }

    return best_node;
}

int main(){
    if(now_status == file_status::local){
        read_input();
        file_output();
    }
    input();
    hash_init();

    for(int i = 0; i < N; i++){
        for(int j = 0; j < N; j++){
            if(grid[i][j].status == cell_status::player){
                sy = i, sx = j;
            }
            else if(grid[i][j].status == cell_status::key){
                ky = i, kx = j;
            }
            else if(grid[i][j].status == cell_status::goal){
                gy = i, gx = j;
            }
        }
    }
    Player player(sy, sx);

    node init_node(player);
    node best_node = BeamSearch(init_node);
    pii start(best_node.player.y, best_node.player.x);
	pii key(ky, kx), goal(gy, gx);

    for(auto &query : best_node.actions){
        cout << query << endl;
    }
	if(!best_node.player.get_key){
		vector<string> path_to_key = CalcMinDistance(best_node, start, key).second;
		int siz = path_to_key.size();
		for(auto &query : path_to_key){
			cout << query << endl;
		}
		best_node.now_turn += siz;
		start = key;
	}
	vector<string> path_to_goal = CalcMinDistance(best_node, start, goal).second;
	for(auto &query : path_to_goal){
		cout << query << endl;
	}

    return 0;
}

yukicoder

結果

テストケース

ソースコード