結果
| 問題 | No.5015 Escape from Labyrinth |
| ユーザー |
 FplusFplusF
|
| 提出日時 | 2023-04-16 13:12:50 |
| 言語 | C++17(gcc12) (gcc 12.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 1,919 ms / 3,000 ms |
| コード長 | 12,860 bytes |
| コンパイル時間 | 3,319 ms |
| コンパイル使用メモリ | 248,428 KB |
| 実行使用メモリ | 63,948 KB |
| スコア | 114,880 |
| 最終ジャッジ日時 | 2023-04-16 13:14:35 |
| 合計ジャッジ時間 | 99,614 ms |
|
ジャッジサーバーID （参考情報） |
judge15 / judge13 |
| 純コード判定しない問題か言語 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 100 |
ソースコード
#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{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){ret.score=-1e9;ret.hp=-1e9;return ret;}}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;queue<pair<int,int>> q;q.push({gi,gj});vector<vector<int>> dist(input.n,vector<int>(input.n,-1));dist[gi][gj]=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});}}}if(dist[si][sj]==-1) return "";int ni=si,nj=sj;while(ni!=gi||nj!=gj){int x=0;rep(k,4){int ti=ni+pi[k],tj=nj+pj[k];if(outside(ti,tj)) continue;if(dist[ti][tj]==dist[ni][nj]-1){x=k;if(input.s[ti][tj]=='J') break;}}int ti=ni+pi[x],tj=nj+pj[x];ni=ti;nj=tj;ret.push_back(dir[x]);}return ret;}string min_path_v(int si,int sj,int gi,int gj,vector<pair<int,int>> &v){if((int)v.size()==0){return min_path(si,sj,gi,gj);}string ret;ret+=min_path(si,sj,v.front().first,v.front().second);rep(i,(int)v.size()-1){ret+=min_path(v[i].first,v[i].second,v[i+1].first,v[i+1].second);}ret+=min_path(v.back().first,v.back().second,gi,gj);return ret;}string v_to_root(vector<pair<int,int>> &v){string ret;rep(i,v.size()-1){ret+=min_path(v[i].first,v[i].second,v[i+1].first,v[i+1].second);}return ret;}string v_to_root(vector<pair<int,int>> &first_v,int si,int sj,vector<pair<int,int>> &v,int gi,int gj){vector<pair<int,int>> new_v;for(auto &i:first_v) new_v.emplace_back(i);if(new_v.size()==0||(new_v.back().first!=si||new_v.back().second!=sj)) new_v.emplace_back(si,sj);for(auto &i:v){if(i==new_v.back()) continue;new_v.emplace_back(i);}if(new_v.size()==0||(new_v.back().first!=gi||new_v.back().second!=gj)) new_v.emplace_back(gi,gj);return v_to_root(new_v);}vector<pair<int,int>> v_to_v(vector<pair<int,int>> &first_v,int si,int sj,vector<pair<int,int>> &v,int gi,int gj){vector<pair<int,int>> new_v;for(auto &i:first_v) new_v.emplace_back(i);if(new_v.size()==0||(new_v.back().first!=si||new_v.back().second!=sj)) new_v.emplace_back(si,sj);for(auto &i:v){if(i==new_v.back()) continue;new_v.emplace_back(i);}if(new_v.size()==0||(new_v.back().first!=gi||new_v.back().second!=gj)) new_v.emplace_back(gi,gj);return new_v;}vector<pair<int,int>> solve_root(vector<pair<int,int>> first_v,int si,int sj,int gi,int gj,int min_hp,vector<vector<vector<vector<int>>>>&dist_juwel){vector<pair<int,int>> v;int ni=si,nj=sj;while(true){vector<vector<bool>> visited=play(v_to_root(first_v,si,sj,v,gi,gj)).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;v.emplace_back(ti,tj);result res=play(v_to_root(first_v,si,sj,v,gi,gj));if(res.hp<=min_hp){v.pop_back();if(first_flag) end_flag=true;break;}ni=ti;nj=tj;visited=res.visited;first_flag=false;}if(end_flag) break;int n=v.size();if(n==0) break;vector<pair<int,int>> pre_v=v;while(true){bool reversed=false;rep(i,n-1){for(int j=i+2;j<n-1;j++){int x=dist_juwel[v[i].first][v[i].second][v[i+1].first][v[i+1].second];int y=dist_juwel[v[j].first][v[j].second][v[j+1].first][v[j+1].second];int a=dist_juwel[v[i].first][v[i].second][v[j].first][v[j].second];int b=dist_juwel[v[i+1].first][v[i+1].second][v[j+1].first][v[j+1].second];if(a+b<x+y){reverse(v.begin()+i+1,v.begin()+j+1);reversed=true;break;}}if(reversed) break;}if(!reversed) break;}if(play(v_to_root(first_v,si,sj,v,gi,gj)).hp<=min_hp){v=pre_v;break;}ni=v.back().first;nj=v.back().second;}return v_to_v(first_v,si,sj,v,gi,gj);}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);}}pair<int,vector<pair<int,int>>> ans={(int)-1e9,{}};vector<pair<int,int>> v;v={{input.si,input.sj},{input.ki,input.kj}};v=solve_root(v,input.ki,input.kj,input.gi,input.gj,0,dist_juwel);chmax(ans,{play(v_to_root(v)).score,v});for(auto &i:v_to_root(ans.second)){cout << "M " << i << '\n';}}}solver;int main(){ios::sync_with_stdio(false);cin.tie(nullptr);input.input_cin();solver.solve();}