Submission #257227

#TimeUsernameProblemLanguageResultExecution timeMemory
257227aggu_01000101Robots (APIO13_robots)C++14
30 / 100
289 ms106360 KiB
#include <iostream> #include <bits/stdc++.h> #include <assert.h> #include <algorithm> #include <vector> #include <set> #include <string> #include <queue> #include <map> #include <iomanip> #define initrand mt19937 mt_rand(time(0)); #define rand mt_rand() //#define int long long #define INF 1000000000 #define mid(l, u) ((l+u)/2) #define lchild(i) (i*2 + 1) #define rchild(i) (i*2 + 2) using namespace std; const int H = 501; string m[H]; int dp[H][H][10][10]; pair<int, int> final[H][H][4]; vector<pair<int, int>> adj[H][H]; int n, h, w; int A(int x){ return ((x+1)%4); } int C(int x){ return ((x-1+4)%4); } bool valid(pair<int, int> x){ if(x.first < 0 || x.second<0) return false; if(x.first >= h || x.second >= w) return false; return m[x.first][x.second] != 'x'; } pair<int, int> update(pair<int, int> x, int dir){ if(dir==0){ x.first++; return x; } if(dir==1){ x.second++; return x; } if(dir==2){ x.first--; return x; } x.second--; return x; } pair<int, int> nxt(pair<int, int> curr, int &dir){ if(m[curr.first][curr.second]=='C') dir = C(dir); else if(m[curr.first][curr.second]=='A') dir = A(dir); if(!valid(update(curr, dir))) return curr; return update(curr, dir); } pair<int, int> dfs(int i, int j, int dir){ if(final[i][j][dir].first >=0){ return final[i][j][dir]; } else if(final[i][j][dir].first==-1){ return {-1, -1}; } final[i][j][dir] = {-1, -1}; int currd = dir; pair<int, int> togo = nxt({i, j}, dir); if(togo.first == i && togo.second == j){ //cout<<i<<" "<<j<<" in direction "<<dir<<" can't move"<<endl; return final[i][j][currd] = {i, j}; } final[i][j][currd] = dfs(togo.first, togo.second, dir); //cout<<i<<" "<<j<<" in direction "<<currd<<" leads to "<<final[i][j][currd].first<<" "<<final[i][j][currd].second<<endl; return final[i][j][currd]; } void BFS(pair<int, int> curr, int st){ for(int i =0 ;i<h;i++){ for(int j = 0;j<w;j++) dp[i][j][st][st] = INF; } dp[curr.first][curr.second][st][st] = 0; queue<pair<int, int>> q; q.push(curr); while(!q.empty()){ curr = q.front(); q.pop(); for(pair<int, int> k: adj[curr.first][curr.second]){ if(dp[k.first][k.second][st][st] < INF) continue; dp[k.first][k.second][st][st] = dp[curr.first][curr.second][st][st] + 1; q.push(k); } } } signed main(){ ios_base::sync_with_stdio(false); cin.tie(NULL); cin>>n>>w>>h; for(int i =0 ;i<h;i++) cin>>m[i]; //dir 0 -> i++ //dir 1 -> j++ //dir 2 -> i-- //dir 3 -> j-- for(int i =0 ;i<h;i++){ for(int j =0 ;j<w;j++){ for(int k = 0;k<4;k++) final[i][j][k] = {-2, -2}; } } for(int i = 0;i<h;i++){ for(int j = 0;j<w;j++){ for(int k = 0;k<4;k++){ if(m[i][j]=='x') continue; pair<int, int> ta = dfs(i, j, k); //cout<<i<<" "<<j<<" "<<k<<" leads to ("<<ta.first<<", "<<ta.second<<")"<<endl; if(ta.first != -1){ adj[i][j].push_back(ta); } } } } for(int i = 0;i<h;i++){ for(int j = 0;j<w;j++){ if(m[i][j]=='A' || m[i][j]=='C' || m[i][j]=='x' || m[i][j]=='.') continue; int curr = m[i][j] - '0'; BFS({i, j}, curr); } } vector<pair<int, int>> dPush[50000]; for(int sz = 1;sz<n;sz++){ for(int st = 1;(st+sz)<=n;st++){ int sd = (st+sz); pair<int, int> toPush; int minCost = INF; for(int i =0 ;i<h;i++){ for(int j = 0;j<w;j++){ dp[i][j][st][sd] = INF; for(int k = st;k<sd;k++) dp[i][j][st][sd] = min(dp[i][j][st][k] + dp[i][j][k+1][sd], dp[i][j][st][sd]); if(dp[i][j][st][sd] < INF){ minCost = min(minCost, dp[i][j][st][sd]); dPush[dp[i][j][st][sd]].push_back({i, j}); } } } if(minCost == INF) continue; queue<pair<int, int>> q; for(pair<int, int> j: dPush[minCost]) q.push({j.first, j.second}); dPush[minCost].clear(); while(!q.empty()){ pair<int, int> curr = q.front(); q.pop(); int i = curr.first, j = curr.second; int cd = dp[i][j][st][sd]; for(pair<int, int> nxt: dPush[cd+1]){ if(dp[nxt.first][nxt.second][st][sd] < (cd+1)) continue; dp[nxt.first][nxt.second][st][sd] = cd + 1; q.push(nxt); } dPush[cd+1].clear(); for(pair<int, int> nxt: adj[i][j]){ if(dp[nxt.first][nxt.second][st][sd] <= (cd+1)) continue; dp[nxt.first][nxt.second][st][sd] = cd + 1; q.push({nxt.first, nxt.second}); } } for(int i =0 ;i<h;i++){ for(int j = 0;j<w;j++){ int k = INF; for(int kk = st;kk<sd;kk++) k = min(dp[i][j][st][kk] + dp[i][j][kk+1][sd], k); if(k<INF) dPush[k].clear(); } } } } int ans = INF; for(int i =0 ;i<h;i++){ for(int j =0;j<w;j++){ ans = min(ans, dp[i][j][1][n]); } } if(ans >= INF) ans = -1; cout<<ans<<endl; } /* 4 10 5 1......... AA...x4... ..A..x.... 2....x.... ..C.3.A... */
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...