結果

問題 No.5015 Escape from Labyrinth
ユーザー a9ua1i0n
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

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

#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;
else
score += 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 search
board 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;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0