結果
問題 | No.5015 Escape from Labyrinth |
ユーザー |
|
提出日時 | 2023-04-16 19:07:25 |
言語 | C++11 (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 2,622 ms / 3,000 ms |
コード長 | 10,443 bytes |
コンパイル時間 | 2,958 ms |
コンパイル使用メモリ | 197,996 KB |
実行使用メモリ | 98,928 KB |
スコア | 13,760 |
最終ジャッジ日時 | 2023-04-16 19:11:55 |
合計ジャッジ時間 | 269,851 ms |
ジャッジサーバーID (参考情報) |
judge12 / judge16 |
純コード判定しない問題か言語 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 100 |
ソースコード
#include <bits/stdc++.h>using namespace std;const int grid_size = 60; // 迷宮の大きさconst int max_hp = 1500; // 初期体力int dy[4] = {-1, 1, 0, 0};int dx[4] = {0, 0, -1, 1};string dir = "UDLR";// 探知機の情報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;}};// 範囲外かどうか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;}class action {public:virtual void print() = 0;};// class pause: public action {// public:// void print() override {// cout << "S"// << "\n";// }// };class transfer: public action {char dir;public:transfer(char dir):dir(dir) {}void print() {cout << "M " << this->dir<< "\n";}};// class fire: public action {// char dir;// public:// fire(char dir):// dir(dir) {}// void print() override {// cout << "F " << this->dir// << "\n";// }// };// BFSによる経路探索vector<transfer> find_path(int sy, int sx, int gy, int gx, vector<string>& S) {int siz = S.size();vector<vector<int>> dist(siz, vector<int>(siz, -1));dist[sy][sx] = 0;queue<pair<int, int>> q;q.emplace(sy, sx);while (!q.empty()) {pair<int, int> p = q.front();q.pop();int y = p.first, x = p.second;for (int k = 0; k < 4; k++) {int ny = y + dy[k], nx = x + dx[k];if (range_out(ny, nx))continue;if (dist[ny][nx] != -1)continue;char cell = S[ny][nx];if (cell == '#' || cell == 'B' || cell == 'E')continue;dist[ny][nx] = dist[y][x] + 1;q.emplace(ny, nx);}}vector<transfer> res;if (dist[gy][gx] == -1)return res;int now_y = gy, now_x = gx, now_d = dist[gy][gx];while (now_y != sy || now_x != sx) {bool moved = false;for (int k = 0; k < 4; k++) {int new_y = now_y + dy[k], new_x = now_x + dx[k];if (range_out(new_y, new_x))continue;if (dist[new_y][new_x] != now_d - 1)continue;now_y = new_y, now_x = new_x;now_d--;res.push_back(transfer(dir[k ^ 1]));moved = true;break;}assert(moved);}reverse(res.begin(), res.end());return res;}pair<int, int> start_yx;pair<int, int> goal_yx;pair<int, int> key_yx;int dist(pair<int, int> pos, int y, int x) {return abs(pos.first - y) + abs(pos.second - x);}class board {public:vector<transfer> ans;bitset<500> gem;int hp = 1500;int powder = 0;int y = 0;int x = 0;bool has_key = false;board(int y, int x):y(y), x(x) {}board(int y, int x, vector<transfer>& ans, bitset<500> gem, int hp, int powder, bool has_key):y(y), x(x), ans(ans), gem(gem), hp(hp), powder(powder), has_key(has_key) {}};int get_score(const board& b) {int score = 0;score += b.gem.count() * 10;// score += b.hp;if (b.has_key)score += (grid_size * 2 - dist(goal_yx, b.y, b.x)) * 10;elsescore += grid_size * 2 - dist(key_yx, b.y, b.x);// if (b.has_key)// score *= 10;return score;}bool operator<(const board& t1, const board& t2) {return get_score(t1) < get_score(t2);};bool operator>(const board& t1, const board& t2) {return t2 < t1;}bool operator<=(const board& t1, const board& t2) {return !(t1 > t2);}bool operator>=(const board& t1, const board& t2) {return !(t1 < t2);}int check_damages(vector<vector<set<int>>>& is_detectedable, vector<enemy>& E, int y, int x, int turn) {int damages = 0;for (auto itr = is_detectedable[y][x].begin(); itr != is_detectedable[y][x].begin(); itr++) {if (turn % E[*itr].d == 0) {damages++;}}return damages;}void wrapper(action& act) {act.print();}int main() {ios::sync_with_stdio(false);cin.tie(nullptr);auto start = clock();// 入力の受け取りint N, D, H;cin >> N >> D >> H;vector<string> S(N);for (int i = 0; i < N; i++)cin >> S[i];int M;cin >> M;vector<enemy> E;for (int i = 0; i < M; i++) {int y, x, d;cin >> y >> x >> d;E.emplace_back(y, x, d, i);}vector<vector<set<int>>> is_detectedable(N, vector<set<int>>(N));for (int i = 0; i < M; i++) {for (int d = 0; d < 4; d++) {int y = E[i].y + dy[d];int x = E[i].x + dx[d];while (!range_out(y, x)) {if (S[y][x] == '#' || S[y][x] == 'E') {break;}is_detectedable[y][x].insert(i);y += dy[d];x += dx[d];}}}map<int, map<int, int>> gems;map<int, map<int, int>> powders;{int g = 0;int p = 0;for (int i = 0; i < N; i++) {for (int j = 0; j < N; j++) {if (S[i][j] == 'S') {start_yx = pair<int, int>(i, j);}if (S[i][j] == 'G') {goal_yx = pair<int, int>(i, j);}if (S[i][j] == 'K') {key_yx = pair<int, int>(i, j);}if (S[i][j] == 'J') {gems[i][j] = g;g++;}if (S[i][j] == 'J') {powders[i][j] = p;p++;}}}}// beam searchboard best_ans = board(start_yx.first, start_yx.second);int beam_width = 5000;int it = 0;priority_queue<board, vector<board>, less<board>> que, nque;que.push(best_ans);vector<transfer> find_key = find_path(start_yx.first, start_yx.second, key_yx.first, key_yx.second, S);vector<transfer> goal = find_path(key_yx.first, key_yx.second, goal_yx.first, goal_yx.second, S);best_ans.ans.insert(best_ans.ans.end(), find_key.begin(), find_key.end());best_ans.ans.insert(best_ans.ans.end(), goal.begin(), goal.end());while ((clock() - start) < 2.5 * CLOCKS_PER_SEC) {// cerr << "queue.top: " << que.top().hp << " " << que.top().gem.count() << " " << boolalpha << que.top().has_key << " " << que.top().x << "" << que.top().y << " : " << get_score(que.top())// << "\n";if (que.empty())break;it++;for (int w = 0; w < beam_width; w++) {if (que.empty()) {break;}auto b = que.top();que.pop();for (int d = 0; d < 4; d++) {int ny = b.y + dy[d];int nx = b.x + dx[d];if (range_out(ny, nx)) {continue;}bool can_push = true;int nhp = b.hp - 1;if (nhp <= 0) {continue;}int npowder = b.powder;bitset<500> ngem = b.gem;bool key = b.has_key;switch (S[ny][nx]) {case '.':nhp -= D * check_damages(is_detectedable, E, ny, nx, b.ans.size() + 1);break;case '#':can_push = false;break;case 'S':nhp -= D * check_damages(is_detectedable, E, ny, nx, b.ans.size() + 1);break;case 'G':if (b.has_key) {// cerr << "ans"// << "\n";auto nb = board(ny, nx, b.ans, ngem, nhp, npowder, b.has_key);nb.ans.push_back(transfer(dir[d]));if (best_ans < nb) {// cerr << "ans"// << " " << nb.gem.count()// << "\n";best_ans = nb;}can_push = false;} else {nhp -= D * check_damages(is_detectedable, E, ny, nx, b.ans.size() + 1);}break;case 'K':nhp -= D * check_damages(is_detectedable, E, ny, nx, b.ans.size() + 1);key = true;break;case 'J':nhp -= D * check_damages(is_detectedable, E, ny, nx, b.ans.size() + 1);ngem[gems[ny][nx]] = true;break;case 'F':nhp -= D * check_damages(is_detectedable, E, ny, nx, b.ans.size() + 1);// TODO: powder取得break;case 'E':can_push = false;break;default:break;}if (!can_push) {continue;}if (nhp <= 0) {continue;}auto nb = board(ny, nx, b.ans, ngem, nhp, npowder, key);nb.ans.push_back(transfer(dir[d]));nque.push(nb);}// b.ans.push_back(pause());// b.hp--;// if (b.hp > 0)// nque.push(b);}que = nque;priority_queue<board, vector<board>, less<board>> e;swap(nque, e);}cerr << "iter: " << it << "\n";cerr << "best-ans: " << best_ans.ans.size() << "\n";for (auto itr = best_ans.ans.begin(); itr != best_ans.ans.end(); itr++) {wrapper(*itr);}return 0;}