結果

問題 No.5015 Escape from Labyrinth
ユーザー platinum
提出日時 2023-04-15 11:35:46
言語 C++17(gcc12)
(gcc 12.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 30,754 bytes
コンパイル時間 5,268 ms
コンパイル使用メモリ 229,972 KB
実行使用メモリ 415,020 KB
スコア 159,500
最終ジャッジ日時 2023-04-15 11:40:19
合計ジャッジ時間 163,152 ms
ジャッジサーバーID
（参考情報） 		judge14 / judge16
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 91 WA * 9
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#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){
            return -1;
        }
        else if(grid[ny][nx].status == cell_status::block){
            //return -1;
        }
        else if(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 = 1;
        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.actions.emplace_back(query);
    char c = query[0];
    if(c == 'S') return;
    int k = get_direction(query[2]);
    if(c == 'M'){
        v.player.move(k);
        int y = v.player.y;
        int x = v.player.x;
        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){
                    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()) break;
            }
            y += dy[k]; x += dx[k];
        }
    }
}
// プレイヤーへのダメージ計算
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 % enemy[e_num].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;
}
 // 戻り値 0 : 探知されない, 1 : 探知される, 2 : 破壊しても探知される
int WillDetected(node &v, int k, bool repeat = true){
    int py = v.player.y, px = v.player.x;
    int y = py + dy[k], x = px + dx[k];
    while(!range_out(y, x)){
        if(grid[y][x].status == cell_status::wall){
            return 0;
        }
        else if(grid[y][x].status == cell_status::enemy){
            bool destroyed = false;
            int e_num = enemy_number[y][x];
            for(auto &num : v.enemy_destroyed){
                if(e_num == num){
                    destroyed = true;
                    break;
                }
            }
            if(!destroyed){
                if(v.now_turn % enemy[e_num].d == 0){
                    if(!repeat) return 1;
                    else{
                        v.player.y = y; v.player.x = x;
                        int res = WillDetected(v, k, false);
                        v.player.y = py; v.player.x = px;
                        if(res == 0) return 1;
                        else return 2;
                    }
                }
                else return 0;
            }
        }
        else{
            auto itr = v.block_pos.find(y * grid_size + x);
            if(itr != v.block_pos.end()) return 0;
        }
        y += dy[k]; x += dx[k];
    }
    return 0;
}
void DecideActions(node &v, string path){
    // 後ろから見て行く
    while(!path.empty()){
        char c = path.back();
        int k = get_direction(c);
        string query;
        // 移動先で探知されないなら動く
        v.player.y += dy[k]; v.player.x += dx[k];
        int move_damage = CalcDamage(v);
        v.player.y -= dy[k]; v.player.x -= dx[k];
        if(move_damage > 1){
            // 動かないで探知されないなら何もしない
            int stand_damage = CalcDamage(v);
            if(stand_damage > 1){
                // 動かない方が損なら動く
                if(move_damage < stand_damage){
                    query = "M ";
                    query += c;
                }
                // そうでないなら防御
                else{
                    for(int direction = 0; direction < 4; direction++){
                        if(direction == k) continue;
                        int detected = WillDetected(v, direction);
                        int ny = v.player.y + dy[direction];
                        int nx = v.player.x + dx[direction];
                        if(range_out(ny, nx)) continue;
                        if(grid[ny][nx].status == 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){
                                if(detected == 1 && v.player.fire > 0){
                                    query = "F ";
                                    query += c;
                                    break;
                                }
                                else continue;
                            }
                        }
                        else if(grid[ny][nx].status == cell_status::jewel){
                            bool picked = false;
                            int j_num = jewel_number[ny][nx];
                            for(auto &num : v.picked_jewel){
                                if(j_num == num){
                                    picked = true;
                                    break;
                                }
                            }
                            if(!picked){
                                if(detected == 1 && v.player.fire > 0){
                                    query = "F ";
                                    query += c;
                                    break;
                                }
                                else continue;                              
                            }
                        }
                        else if(grid[ny][nx].status == cell_status::fire){
                            bool picked = false;
                            int f_num = fire_number[ny][nx];
                            for(auto &num : v.picked_fire){
                                if(f_num == num){
                                    picked = true;
                                    break;
                                }
                            }
                            if(!picked){
                                if(detected == 1 && v.player.fire > 0){
                                    query = "F ";
                                    query += c;
                                    break;
                                }
                                else continue;                              
                            }
                        }
                        if(detected == 0) continue;
                        else if(detected == 1){
                            if(v.player.fire > 0){
                                query = "F ";
                                query += dir[direction];
                            }
                            else{
                                query = "B ";
                                query += dir[direction];
                            }
                        }
                        else{
                            query = "B ";
                            query += dir[direction];
                        }
                        break;
                    }
                }
            }
            else{
                query = "S";
            }
        }
        else{
            query = "M ";
            query += c;
        }
        if(query.empty()){
            query = "M ";
            query += c;
        }
        update_actions(v, query);
        int d = CalcDamage(v);
        v.player.damage(d);
        v.now_turn++;
        if(query[0] == 'M') path.pop_back();
    }
}
void 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);
        }
    }
    // 経路復元
    if(dist[ty-min_y][tx-min_x] == -1) return;
    string path;
    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--;
            path.push_back(dir[k^1]);
            moved = true;
            break;
        }
        assert(moved);
    }
    DecideActions(v, path);
}
// ゴールまでの最小の体力減少値をダイクストラ法で見積もる
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 < 300 + D * 20 && !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;
                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;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0