#include using std::array, std::vector, std::string; auto start = std::chrono::steady_clock::now(); auto elapsed() { return (std::chrono::steady_clock::now() - start).count(); } constexpr int N = 60; // 迷宮の大きさ constexpr int max_hp = 1500; // 初期体力 constexpr int dy[4] = {-1, 1, 0, 0}; constexpr int dx[4] = {0, 0, -1, 1}; constexpr auto dir = "UDLR"; enum { EMPTY, BLOCK, E2, E3, E4, E5, WALL, JEWELL, FIRE, KEY, GOAL }; // 範囲外かどうか bool range_out(size_t y, size_t x) { return x >= N or y >= N; } // 探知機の情報 struct enemy { int y, x, d; enemy(int y, int x, int d) : y(y), x(x), d(d) {} }; int ky, kx; int gy, gx; array distance, distance_key; // 盤面の情報 struct Board { array board; int score = 0; int fire = 0; int hp = max_hp; int block = 0; bool key = false; bool escaped = false; int y, x; int turn = 0; int first_action = -1; Board(const vector &S, const vector &E) { board.fill(EMPTY); for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { const int idx = 64 * i + j; switch (S[i][j]) { case '#': board[idx] = WALL; break; case 'J': board[idx] = JEWELL; break; case 'F': board[idx] = FIRE; break; case 'K': board[idx] = KEY; ky = i; kx = j; break; case 'G': board[idx] = GOAL; gy = i; gx = j; break; case 'S': y = i; x = j; break; } } } for (const auto &[i, j, d] : E) { board[64 * i + j] = d; } } int evaluate() const { int res = 0; if (key) { res -= distance[64 * y + x]; } else { res -= distance[64 * ky + kx] + distance_key[64 * y + x]; } res -= block; res *= 2; res += 10000 * score + hp; return res; } // action: 0 to 12 // return: is_legal bool advance(const int action) { turn++; const int d = action & 3; int ny = y + dy[d], nx = x + dx[d]; if (action < 4) { // move if (range_out(ny, nx)) return false; int &state = board[64 * ny + nx]; y = ny; x = nx; if (state == WALL or state == BLOCK or (2 <= state and state <= 5)) { return false; } else if (state == KEY) { key = true; state = EMPTY; } else if (state == JEWELL) { score++; state = EMPTY; } else if (state == FIRE) { fire++; state = EMPTY; } else if (state == GOAL and key) { escaped = true; } return true; } else if (action < 8) { // block if (range_out(ny, nx)) return false; if (board[64 * ny + nx] >= 2) return false; block -= board[64 * ny + nx]; board[64 * ny + nx] = 1 - board[64 * ny + nx]; block += board[64 * ny + nx]; return true; } else if (action < 12) { // fire if (fire == 0) return false; while (not range_out(ny, nx)) { int state = board[64 * ny + nx]; if (2 <= state and state <= 5) { // enemy board[64 * ny + nx] = EMPTY; fire--; return true; } else if (state == WALL or state == BLOCK) { return false; } ny += dy[d]; nx += dx[d]; } return false; } else { return true; } } void after() { for (int d = 0; d < 4; d++) { int y_next = y + dy[d], x_next = x + dx[d]; while (not range_out(y_next, x_next)) { int state = board[64 * y_next + x_next]; if (2 <= state and state <= 5) { // enemy if (turn % state == 0) hp -= d; break; } if (state == WALL or state == BLOCK) break; y_next += dy[d]; x_next += dx[d]; } } hp--; } }; bool operator<(const Board &a, const Board &b) { return a.evaluate() < b.evaluate(); } int beam_search(const Board &board, const int beam_width, const int beam_depth) { std::priority_queue beam; Board best_board{board}; beam.emplace(board); for (int t = 0; t < beam_depth; t++) { std::priority_queue next_beam; for (int i = 0; i < beam_width; i++) { if (beam.empty()) break; Board board_now{beam.top()}; beam.pop(); for (int action = 0; action < 13; action++) { if (4 <= action and action < 13) continue; Board board_next{board_now}; if (not board_next.advance(action)) continue; if (not board_next.escaped) { board_next.after(); } if (board_next.hp <= 0) continue; if (t == 0) { board_next.first_action = action; } next_beam.emplace(board_next); } } beam = next_beam; best_board = beam.top(); if (best_board.escaped) break; } return best_board.first_action; } int main() { // 入力の受け取り int N, D, H; std::cin >> N >> D >> H; vector S(N); for (int i = 0; i < N; i++) std::cin >> S[i]; int M; std::cin >> M; vector E; for (int i = 0; i < M; i++) { int y, x, d; std::cin >> y >> x >> d; E.emplace_back(y, x, d); } Board board(S, E); std::queue que; distance.fill(N * N); distance[64 * gy + gx] = 0; que.push(64 * gy + gx); while (not que.empty()) { int idx = que.front(); que.pop(); int y0 = idx / 64, x0 = idx % 64; for (int d = 0; d < 4; d++) { int ny = y0 + dy[d], nx = x0 + dx[d]; if (range_out(ny, nx)) continue; int state = S[ny][nx]; if (state == '#' or state == 'E') { continue; } if (distance[64 * ny + nx] != N * N) continue; distance[64 * ny + nx] = distance[idx] + 1; que.push(64 * ny + nx); } } distance_key.fill(N * N); distance_key[64 * ky + kx] = 0; que.push(64 * ky + kx); while (not que.empty()) { int idx = que.front(); que.pop(); int y0 = idx / 64, x0 = idx % 64; for (int d = 0; d < 4; d++) { int ny = y0 + dy[d], nx = x0 + dx[d]; if (range_out(ny, nx)) continue; int state = S[ny][nx]; if (state == '#' or state == 'E') { continue; } if (distance_key[64 * ny + nx] != N * N) continue; distance_key[64 * ny + nx] = distance_key[idx] + 1; que.push(64 * ny + nx); } } while (not board.escaped) { int action = beam_search(board, 100, 4); if (action == -1) break; if (action < 4) { std::cout << "M " << dir[action] << std::endl; } else if (action < 8) { std::cout << "B " << dir[action & 3] << std::endl; } else if (action < 12) { std::cout << "F " << dir[action & 3] << std::endl; } else { std::cout << "S" << std::endl; } board.advance(action); board.after(); } return 0; }