Submission #477904

#TimeUsernameProblemLanguageResultExecution timeMemory
477904bin1st090104Robots (APIO13_robots)C++11
100 / 100
546 ms151332 KiB
#include <bits/stdc++.h> using namespace std; int const maxK=9; int const maxN=5e2; int const inf=0x3f3f3f3f; int K,N,M; char c[maxN+3][maxN+3]; int dx[]={-1,0,1,0}; int dy[]={0,1,0,-1}; pair<int,int> F[maxN+3][maxN+3][4],F_null={0,0}; int G[maxK+3][maxK+3][maxN+3][maxN+3]; pair<int,int> Cal_F(int i,int j,int d){ if(F[i][j][d]!=F_null){ return F[i][j][d]; } pair<int,int>&Res=F[i][j][d]; int newd=d; if(c[i][j]=='A'){ --newd; if(newd<0){ newd+=4; } } if(c[i][j]=='C'){ ++newd; if(newd>=4){ newd-=4; } } int u=i+dx[newd]; int v=j+dy[newd]; if(u<1||N<u||v<1||M<v||c[u][v]=='x'){ Res={i,j}; } else{ Res=Cal_F(u,v,newd); } return Res; } struct Data{ int i,j,x; Data(int i=0,int j=0,int x=0):i(i),j(j),x(x){} }; bool Gmin(int&x,int y){ return x>y?x=y,true:false; } int main(){ cin.tie(nullptr)->sync_with_stdio(false); cin>>K>>M>>N; for(int i=1;i<=N;++i){ cin>>c[i]+1; } for(int i=1;i<=N;++i){ for(int j=1;j<=M;++j){ for(int d=0;d<4;++d){ if(c[i][j]!='x'){ Cal_F(i,j,d); } } } } memset(G,0x3f,sizeof G); for(int i=1;i<=N;++i){ for(int j=1;j<=M;++j){ if(isdigit(c[i][j])){ G[c[i][j]-'0'][c[i][j]-'0'][i][j]=0; } } } vector<Data> Sta,Tmp; Sta.reserve(N*M); Tmp.reserve(N*M); for(int r=1;r<=K;++r){ for(int l=r;l>=1;--l){ for(int i=1;i<=N;++i){ for(int j=1;j<=M;++j){ for(int k=l;k<r;++k){ G[l][r][i][j]=min(G[l][r][i][j],G[l][k][i][j]+G[k+1][r][i][j]); } if(G[l][r][i][j]!=inf){ Sta.push_back(Data(i,j,G[l][r][i][j])); } } } sort(Sta.begin(),Sta.end(), [&](Data const&lhs,Data const&rhs){ return lhs.x>rhs.x; }); while(!Sta.empty()){ int Val=Sta.back().x; while(!Sta.empty()&&Sta.back().x==Val){ Tmp.push_back(Sta.back()); Sta.pop_back(); } while(!Tmp.empty()){ int i=Tmp.back().i; int j=Tmp.back().j; int x=Tmp.back().x; Tmp.pop_back(); for(int k=0;k<4;++k){ int u=F[i][j][k].first; int v=F[i][j][k].second; if(Gmin(G[l][r][u][v],x+1)){ Sta.push_back(Data(u,v,G[l][r][u][v])); } } } } } } int Res=inf; for(int i=1;i<=N;++i){ for(int j=1;j<=M;++j){ Gmin(Res,G[1][K][i][j]); } } cout<<(Res==inf?-1:Res); return 0; }

Compilation message (stderr)

robots.cpp: In function 'int main()':
robots.cpp:58:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   58 |   cin>>c[i]+1;
      |        ~~~~^~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...