結果
| 問題 | No.5015 Escape from Labyrinth |
| ユーザー |
 FplusFplusF
|
| 提出日時 | 2023-04-16 14:02:10 |
| 言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 13,246 bytes |
| コンパイル時間 | 5,083 ms |
| コンパイル使用メモリ | 262,172 KB |
| 実行使用メモリ | 67,936 KB |
| スコア | 0 |
| 最終ジャッジ日時 | 2023-04-16 14:02:25 |
| 合計ジャッジ時間 | 12,659 ms |
|
ジャッジサーバーID （参考情報） |
judge12 / judge16 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | TLE | - |
| testcase_01 | -- | - |
| testcase_02 | -- | - |
| testcase_03 | -- | - |
| testcase_04 | -- | - |
| testcase_05 | -- | - |
| testcase_06 | -- | - |
| testcase_07 | -- | - |
| testcase_08 | -- | - |
| testcase_09 | -- | - |
| testcase_10 | -- | - |
| testcase_11 | -- | - |
| testcase_12 | -- | - |
| testcase_13 | -- | - |
| testcase_14 | -- | - |
| testcase_15 | -- | - |
| testcase_16 | -- | - |
| testcase_17 | -- | - |
| testcase_18 | -- | - |
| testcase_19 | -- | - |
| testcase_20 | -- | - |
| testcase_21 | -- | - |
| testcase_22 | -- | - |
| testcase_23 | -- | - |
| testcase_24 | -- | - |
| testcase_25 | -- | - |
| testcase_26 | -- | - |
| testcase_27 | -- | - |
| testcase_28 | -- | - |
| testcase_29 | -- | - |
| testcase_30 | -- | - |
| testcase_31 | -- | - |
| testcase_32 | -- | - |
| testcase_33 | -- | - |
| testcase_34 | -- | - |
| testcase_35 | -- | - |
| testcase_36 | -- | - |
| testcase_37 | -- | - |
| testcase_38 | -- | - |
| testcase_39 | -- | - |
| testcase_40 | -- | - |
| testcase_41 | -- | - |
| testcase_42 | -- | - |
| testcase_43 | -- | - |
| testcase_44 | -- | - |
| testcase_45 | -- | - |
| testcase_46 | -- | - |
| testcase_47 | -- | - |
| testcase_48 | -- | - |
| testcase_49 | -- | - |
| testcase_50 | -- | - |
| testcase_51 | -- | - |
| testcase_52 | -- | - |
| testcase_53 | -- | - |
| testcase_54 | -- | - |
| testcase_55 | -- | - |
| testcase_56 | -- | - |
| testcase_57 | -- | - |
| testcase_58 | -- | - |
| testcase_59 | -- | - |
| testcase_60 | -- | - |
| testcase_61 | -- | - |
| testcase_62 | -- | - |
| testcase_63 | -- | - |
| testcase_64 | -- | - |
| testcase_65 | -- | - |
| testcase_66 | -- | - |
| testcase_67 | -- | - |
| testcase_68 | -- | - |
| testcase_69 | -- | - |
| testcase_70 | -- | - |
| testcase_71 | -- | - |
| testcase_72 | -- | - |
| testcase_73 | -- | - |
| testcase_74 | -- | - |
| testcase_75 | -- | - |
| testcase_76 | -- | - |
| testcase_77 | -- | - |
| testcase_78 | -- | - |
| testcase_79 | -- | - |
| testcase_80 | -- | - |
| testcase_81 | -- | - |
| testcase_82 | -- | - |
| testcase_83 | -- | - |
| testcase_84 | -- | - |
| testcase_85 | -- | - |
| testcase_86 | -- | - |
| testcase_87 | -- | - |
| testcase_88 | -- | - |
| testcase_89 | -- | - |
| testcase_90 | -- | - |
| testcase_91 | -- | - |
| testcase_92 | -- | - |
| testcase_93 | -- | - |
| testcase_94 | -- | - |
| testcase_95 | -- | - |
| testcase_96 | -- | - |
| testcase_97 | -- | - |
| testcase_98 | -- | - |
| testcase_99 | -- | - |
ソースコード
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for (int i=0;i<(int)(n);i++)
#define all(v) v.begin(),v.end()
using ll=long long;
using pll=pair<ll,ll>;
using tll=tuple<ll,ll,ll>;
const ll INF=(1ll<<60);
template<class T> void chmin(T &a,T b){
if(a>b){
a=b;
}
}
template<class T> void chmax(T &a,T b){
if(a<b){
a=b;
}
}
auto start=chrono::system_clock::now();
mt19937 mt;
vector<int> pi={0,1,0,-1},pj={1,0,-1,0};
string dir="RDLU";
struct enemy{
int i,j,d;
};
struct input{
int n,d,h;
vector<string> s;
int m;
vector<enemy> e;
vector<vector<int>> grid_enemy;
int si,sj,ki,kj,gi,gj;
void input_cin(){
cin >> n >> d >> h;
s.resize(n);
rep(i,n) cin >> s[i];
cin >> m;
e.resize(m);
grid_enemy.resize(n);
rep(i,n) grid_enemy[i].resize(n,0);
rep(i,m){
cin >> e[i].i >> e[i].j >> e[i].d;
grid_enemy[e[i].i][e[i].j]=e[i].d;
}
rep(i,n){
rep(j,n){
if(s[i][j]=='S'){
si=i;
sj=j;
}
if(s[i][j]=='K'){
ki=i;
kj=j;
}
if(s[i][j]=='G'){
gi=i;
gj=j;
}
}
}
}
}
input;
struct solver{
vector<vector<double>> grid;
struct result{
int score,hp;
vector<vector<bool>> visited;
};
bool outside(int i,int j){
if(i<0||input.n<=i||j<0||input.n<=j) return true;
else return false;
}
int char_idx(char c){
if(c=='R') return 0;
else if(c=='D') return 1;
else if(c=='L') return 2;
else return 3;
}
int dist_root(vector<pair<int,int>> &v,vector<vector<vector<vector<int>>>> &dist_juwel){
int n=v.size();
int ret=0;
rep(i,n-1){
int d=dist_juwel[v[i].first][v[i].second][v[i+1].first][v[i+1].second];
if(d==-1) return 1e9;
ret+=d;
}
return ret;
}
result play(string &s){
int nt=s.size();
int ni=input.si,nj=input.sj;
vector<vector<bool>> visited(input.n,vector<bool>(input.n));
result ret={0,input.h,visited};
ret.visited[ni][nj]=true;
rep(t,nt){
ni+=pi[char_idx(s[t])];
nj+=pj[char_idx(s[t])];
if(outside(ni,nj)){
ret.score=-1e9;
ret.hp=-1e9;
return ret;
}
if(!ret.visited[ni][nj]&&input.s[ni][nj]=='J') ret.score+=10;
ret.visited[ni][nj]=true;
ret.hp--;
for(int i=ni;0<=i;i--){
if(input.s[i][nj]=='#') break;
if(input.s[i][nj]=='E'){
if((t+1)%input.grid_enemy[i][nj]==0) ret.hp-=input.d;
break;
}
}
for(int i=ni;i<input.n;i++){
if(input.s[i][nj]=='#') break;
if(input.s[i][nj]=='E'){
if((t+1)%input.grid_enemy[i][nj]==0) ret.hp-=input.d;
break;
}
}
for(int j=nj;0<=j;j--){
if(input.s[ni][j]=='#') break;
if(input.s[ni][j]=='E'){
if((t+1)%input.grid_enemy[ni][j]==0) ret.hp-=input.d;
break;
}
}
for(int j=nj;j<input.n;j++){
if(input.s[ni][j]=='#') break;
if(input.s[ni][j]=='E'){
if((t+1)%input.grid_enemy[ni][j]==0) ret.hp-=input.d;
break;
}
}
if(ret.hp<=0) return {(int)-1e9,(int)-1e9};
}
if(ni==input.gi&&nj==input.gj) ret.hp++;
else{
ret.score=-1e9;
//ret.hp=0;
}
return ret;
}
result play_free(int si,int sj,string &s){
int nt=s.size();
int ni=si,nj=sj;
vector<vector<bool>> visited(input.n,vector<bool>(input.n));
result ret={0,input.h,visited};
ret.visited[ni][nj]=true;
rep(t,nt){
ni+=pi[char_idx(s[t])];
nj+=pj[char_idx(s[t])];
if(outside(ni,nj)){
ret.score=-1e9;
ret.hp=-1e9;
return ret;
}
if(!ret.visited[ni][nj]&&input.s[ni][nj]=='J') ret.score+=10;
ret.visited[ni][nj]=true;
ret.hp--;
for(int i=ni;0<=i;i--){
if(input.s[i][nj]=='#') break;
if(input.s[i][nj]=='E'){
if((t+1)%input.grid_enemy[i][nj]==0) ret.hp-=input.d;
break;
}
}
for(int i=ni;i<input.n;i++){
if(input.s[i][nj]=='#') break;
if(input.s[i][nj]=='E'){
if((t+1)%input.grid_enemy[i][nj]==0) ret.hp-=input.d;
break;
}
}
for(int j=nj;0<=j;j--){
if(input.s[ni][j]=='#') break;
if(input.s[ni][j]=='E'){
if((t+1)%input.grid_enemy[ni][j]==0) ret.hp-=input.d;
break;
}
}
for(int j=nj;j<input.n;j++){
if(input.s[ni][j]=='#') break;
if(input.s[ni][j]=='E'){
if((t+1)%input.grid_enemy[ni][j]==0) ret.hp-=input.d;
break;
}
}
if(ret.hp<=0) return {(int)-1e9,(int)-1e9};
}
if(ni==input.gi&&nj==input.gj) ret.hp++;
else{
ret.score=-1e9;
//ret.hp=0;
}
return ret;
}
vector<vector<int>> bfs(int si,int sj){
queue<pair<int,int>> q;
q.push({si,sj});
vector<vector<int>> dist(input.n,vector<int>(input.n,-1));
dist[si][sj]=0;
while(!q.empty()){
int ni,nj;
tie(ni,nj)=q.front();
q.pop();
rep(k,4){
int ti=ni+pi[k],tj=nj+pj[k];
if(outside(ti,tj)) continue;
if(input.s[ti][tj]=='#'||input.s[ti][tj]=='E') continue;
if(dist[ti][tj]==-1){
dist[ti][tj]=dist[ni][nj]+1;
q.push({ti,tj});
}
}
}
return dist;
}
string min_path(int si,int sj,int gi,int gj){
string ret;
priority_queue<tuple<double,int,int>,vector<tuple<double,int,int>>,greater<tuple<double,int,int>>> pq;
pq.push({0,gi,gj});
vector<vector<double>> dist(input.n,vector<double>(input.n,1e9));
vector<vector<pair<int,int>>> per(input.n,vector<pair<int,int>>(input.n));
dist[gi][gj]=0;
while(!pq.empty()){
int d,ni,nj;
tie(d,ni,nj)=pq.top();
pq.pop();
rep(k,4){
int ti=ni+pi[k],tj=nj+pj[k];
if(outside(ti,tj)) continue;
if(input.s[ti][tj]=='#'||input.s[ti][tj]=='E') continue;
if(d+grid[ti][tj]<dist[ti][tj]){
dist[ti][tj]=d+grid[ti][tj];
per[ti][tj]={ni,nj};
pq.push({d+grid[ti][tj],ti,tj});
}
}
}
if(dist[si][sj]==1e9) return "";
int ni=si,nj=sj;
while(ni!=gi||nj!=gj){
rep(k,4){
int ti=ni+pi[k],tj=nj+pj[k];
if(outside(ti,tj)) continue;
if(per[ni][nj]==make_pair(ti,tj)){
ni=ti;
nj=tj;
ret.push_back(dir[k]);
break;
}
}
}
return ret;
}
string solve_root(string first_root,int si,int sj,int gi,int gj,int min_hp,vector<vector<vector<vector<int>>>> &dist_juwel){
string root=first_root;
vector<pair<int,int>> visit_juwel;
int ni=si,nj=sj;
while(true){
vector<vector<bool>> visited=play(root).visited;
bool first_flag=true,end_flag=false;
while(true){
vector<vector<int>> dist=bfs(ni,nj);
pair<int,pair<int,int>> p={(int)1e9,{0,0}};
rep(i,input.n){
rep(j,input.n){
if(dist[i][j]==-1) continue;
if(!visited[i][j]&&input.s[i][j]=='J') chmin(p,{dist[i][j],{i,j}});
}
}
if(p.first==1e9) break;
int ti,tj;
tie(ti,tj)=p.second;
string new_root=root;
new_root+=min_path(ni,nj,ti,tj);
string new_new_root=new_root+min_path(ti,tj,gi,gj);
if(play(new_new_root).hp<=min_hp){
if(first_flag) end_flag=true;
break;
}
visit_juwel.emplace_back(ti,tj);
result res=play(new_root);
ni=ti;
nj=tj;
root=new_root;
visited=res.visited;
first_flag=false;
}
if(end_flag) break;
int n=visit_juwel.size();
if(n==0) break;
while(true){
bool reversed=false;
rep(i,n-1){
for(int j=i+2;j<n-1;j++){
int x=dist_juwel[visit_juwel[i].first][visit_juwel[i].second][visit_juwel[i+1].first][visit_juwel[i+1].second];
int y=dist_juwel[visit_juwel[j].first][visit_juwel[j].second][visit_juwel[j+1].first][visit_juwel[j+1].second];
int a=dist_juwel[visit_juwel[i].first][visit_juwel[i].second][visit_juwel[j].first][visit_juwel[j].second];
int b=dist_juwel[visit_juwel[i+1].first][visit_juwel[i+1].second][visit_juwel[j+1].first][visit_juwel[j+1].second];
if(a+b<x+y){
reverse(visit_juwel.begin()+i+1,visit_juwel.begin()+j+1);
reversed=true;
break;
}
}
if(reversed) break;
}
if(!reversed) break;
}
string new_root=first_root;
if((int)visit_juwel.size()!=0){
new_root+=min_path(si,sj,visit_juwel.front().first,visit_juwel.front().second);
rep(i,n-1){
new_root+=min_path(visit_juwel[i].first,visit_juwel[i].second,visit_juwel[i+1].first,visit_juwel[i+1].second);
}
}
string new_new_root=new_root;
new_new_root+=min_path(visit_juwel.back().first,visit_juwel.back().second,gi,gj);
if(play(new_new_root).hp<=min_hp) break;
root=new_root;
ni=visit_juwel.back().first;
nj=visit_juwel.back().second;
}
root+=min_path(ni,nj,gi,gj);
return root;
}
void solve(){
vector<vector<vector<vector<int>>>> dist_juwel(input.n,vector<vector<vector<int>>>(input.n,vector<vector<int>>(input.n,vector<int>(input.n,-1))));
rep(i,input.n){
rep(j,input.n){
if(input.s[i][j]=='J') dist_juwel[i][j]=bfs(i,j);
}
}
grid.resize(input.n);
rep(ni,input.n){
grid[ni].resize(input.n,11);
rep(nj,input.n){
if(input.s[ni][nj]=='J') grid[ni][nj]-=10;
for(int i=ni;0<=i;i--){
if(input.s[i][nj]=='#') break;
if(input.s[i][nj]=='E'){
grid[ni][nj]+=input.d*(1/input.grid_enemy[i][nj]);
}
}
for(int i=ni;i<input.n;i++){
if(input.s[i][nj]=='#') break;
if(input.s[i][nj]=='E'){
grid[ni][nj]+=input.d*(1/input.grid_enemy[i][nj]);
}
}
for(int j=nj;0<=j;j--){
if(input.s[ni][j]=='#') break;
if(input.s[ni][j]=='E'){
grid[ni][nj]+=input.d*(1/input.grid_enemy[ni][j]);
}
}
for(int j=nj;j<input.n;j++){
if(input.s[ni][j]=='#') break;
if(input.s[ni][j]=='E'){
grid[ni][nj]+=input.d*(1/input.grid_enemy[ni][j]);
}
}
}
}
pair<int,string> ans={(int)-1e9,""};
for(int i=0;i<=input.h;i+=100){
string root="";
root=solve_root(root,input.si,input.sj,input.ki,input.kj,i,dist_juwel);
root=solve_root(root,input.ki,input.kj,input.gi,input.gj,0,dist_juwel);
chmax(ans,{play(root).score,root});
}
for(auto &i:ans.second){
cout << "M " << i << '\n';
}
}
}
solver;
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
input.input_cin();
solver.solve();
}