結果
| 問題 | 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 |
ソースコード
#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;
}