#include #include #include #include #include #include #include #include #include #include using namespace std; using pii = pair; 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 struct v2{ std::vector> v; v2(){} v2(int x){ v.resize(x); } v2(int x, int y){ v.resize(x, std::vector(y)); } v2(int x, int y, T val){ v.resize(x, std::vector(y, val)); } std::vector& 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(y)); } void init(int x, int y, T val){ v.resize(x, std::vector(y, val)); } void push_back(std::vector& 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 struct v3{ std::vector> v; v3(){} v3(int x){ v.resize(x); } v3(int x, int y){ v.resize(x, v2(y)); } v3(int x, int y, int z){ v.resize(x, v2(y, z)); } v3(int x, int y, int z, T val){ v.resize(x, v2(y, z, val)); } v2& operator [] (const int num){ return v[num]; } void init(int x, int y){ v.resize(x, v2(y)); } void init(int x, int y, int z){ v.resize(x, v2(y, z)); } void push_back(v2& e){ v.emplace_back(e); } bool empty(){ return v.empty(); } void clear(){ v.clear(); } }; // ソートされた配列からの探索 bool is_included(vector &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 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& 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& 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> 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; vector S; v2 grid; int sy, sx, ky, kx, gy, gx; v2 enemy_number; v2 jewel_number; vector jewel_pos; v2 fire_number; vector 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 actions; // 盤面の記録 set block_pos; //座標 vector picked_jewel; //番号 vector picked_fire; //番号 vector 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& 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 FindTarget(node& v, int number = 5){ vector 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 jewel_fire_list; // first = マンハッタン距離, second = 座標 vector J = v.picked_jewel; vector 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 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 dist(N, N, -1); dist[py-min_y][px-min_x] = 0; queue 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 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> CalcMinDistance(node& v, pii start, pii goal, bool debug = false){ pair> res; // 最小公倍数 = 60 倍の頂点を用意する const int lcm = 60; int start_t = v.now_turn % lcm; v3 dist(N, N, lcm, INF); v3 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,greater> pq; // 初期盤面を復元(破壊した探知機と生成したブロック) v2 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 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 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> 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 < 250 + D * 25){ continue; } vector target = FindTarget(v); for(auto &pos : target){ node nv = v; vector 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 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 path_to_goal = CalcMinDistance(best_node, start, goal).second; for(auto &query : path_to_goal){ cout << query << endl; } return 0; }