Submission #115668

#TimeUsernameProblemLanguageResultExecution timeMemory
115668ckodserRobots (APIO13_robots)C++14
60 / 100
703 ms163840 KiB
#include <algorithm> #include <bitset> #include <complex> #include <deque> #include <exception> #include <fstream> #include <functional> #include <iomanip> #include <ios> #include <iosfwd> #include <iostream> #include <istream> #include <iterator> #include <limits> #include <list> #include <locale> #include <map> #include <memory> #include <new> #include <numeric> #include <ostream> #include <queue> #include <set> #include <sstream> #include <stack> #include <stdexcept> #include <streambuf> #include <string> #include <typeinfo> #include <utility> #include <valarray> #include <vector> #if __cplusplus >= 201103L #include <array> #include <atomic> #include <chrono> #include <condition_variable> #include <forward_list> #include <future> #include <initializer_list> #include <mutex> #include <random> #include <ratio> #include <regex> #include <scoped_allocator> #include <system_error> #include <thread> #include <tuple> #include <typeindex> #include <type_traits> #include <unordered_map> #include <unordered_set> #endif #define ll int #define pb push_back #define ld long double #define mp make_pair #define F first #define S second #define pii pair<ll,ll> using namespace :: std; const ll maxn=510; const ll inf=1e9+800; const ll di[4]={-1,0 ,+1,0 }; const ll dj[4]={0 ,+1,0 ,-1}; const ll maxm=5e5+500; ll w,h; string s[maxn]; vector<pair<pii,ll> > out[maxn][maxn][4]; bool good[maxn][maxn][4]; vector<ll> inp[maxn*maxn]; ll dp[maxn*maxn][10][10]; inline ll getid(ll a,ll b){ return a*maxn+b; } ll chimishe(char s,ll d){ if(s=='C'){ d=(d+1)%4; }if(s=='A'){ d=(d+3)%4; }return d; } pair<pii,ll> movein(ll i,ll j,ll d){ i+=di[d]; j+=dj[d]; if(i<0 || i>=h || j<0 || j>=w || s[i][j]=='x'){ i-=di[d]; j-=dj[d]; } return mp(mp(i,j),d); } void dfs(ll i,ll j,ll d,ll c){ if(getid(i,j)!=c) inp[getid(i,j)].pb(c); for(auto e:out[i][j][d]){ dfs(e.F.F,e.F.S,e.S,c); } } vector<ll> stk[maxm]; int main(){ ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0); ll n; cin>>n>>w>>h; for(ll i=0;i<h;i++){ cin>>s[i]; } for(ll i=0;i<h;i++){ for(ll j=0;j<w;j++){ if('1'<=s[i][j] && s[i][j]<='9'){ s[i][j]-='1'; } } } for(ll i=0;i<h;i++){ for(ll j=0;j<w;j++){ if(s[i][j]!='x'){ for(ll d=0;d<4;d++){ pair<pii,ll> e=movein(i,j,chimishe(s[i][j],d)); if(e.F.F==i && e.F.S==j){ good[i][j][d]=1; }else{ out[e.F.F][e.F.S][e.S].pb(mp(mp(i,j),d)); } } } } } for(ll i=0;i<h;i++){ for(ll j=0;j<w;j++){ for(ll d=0;d<4;d++){ if(good[i][j][d]){ dfs(i,j,d,getid(i,j)); } } } } for(ll i=0;i<maxn*maxn;i++)for(ll l=0;l<9;l++)for(ll r=0;r<9;r++)dp[i][l][r]=inf; for(ll t=1;t<=n;t++){ for(ll l=0;l+t-1<n;l++){ ll r=l+t-1; ll sz=0; vector<pii> vecc; for(ll i=0;i<h;i++)for(ll j=0;j<w;j++){ ll u=getid(i,j); ll res=inf; if(t==1 && s[i][j]==l){ res=0; } for(ll z=l;z<r;z++){ res=min(res,dp[u][l][z]+dp[u][z+1][r]); } if(res!=inf){ stk[res].pb(u); vecc.pb(mp(res,u)); sz++; } } sort(vecc.begin(),vecc.end()); for(ll w=0;sz!=0;w++){ while(stk[w].size()){ ll v=stk[w].back(); stk[w].pop_back(); sz--; if(dp[v][l][r]>w){ dp[v][l][r]=w; for(auto e:inp[v]){ if(dp[e][l][r]==inf){ stk[w+1].pb(e); sz++; } } } } } } } ll ans=inf; for(ll i=0;i<h;i++)for(ll j=0;j<w;j++){ ans=min(ans,dp[getid(i,j)][0][n-1]); } if(ans==inf){ cout<<-1; }else{ cout<<ans; } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...