Submission #569186

#TimeUsernameProblemLanguageResultExecution timeMemory
569186zaneyuRobots (APIO13_robots)C++14
100 / 100
968 ms114368 KiB
/*input 2 3 1 1x2 */ #include<bits/stdc++.h> using namespace std; //#pragma GCC optimize("unroll-loo8ps,no-stack-protector") //order_of_key #of elements less than x // find_by_order kth element #define ll long long #define ld long double #define pii pair<int,int> #define f first #define s second #define pb push_back #define REP(i,n) for(int i=0;i<n;i++) #define REP1(i,n) for(int i=1;i<=n;i++) #define FIlim(n,x) memset(n,x,sizeof(n)) #define ALL(_a) _a.begin(),_a.end() #define sz(x) (int)x.size() #define SORT_UNIQUE(c) (sort(c.begin(),c.end()),c.resize(distance(c.begin(),unique(c.begin(),c.end())))) const ll INF64=4e18; const ll INF=0x3f3f3f3f; const ll MOD=1e9+7; //const ld PI=acos(-1); const ld eps=1e-9; const int maxn=5e2+5; #define lowb(x) x&(-x) #define MNTO(x,y) x=min(x,(__typeof__(x))y) #define MXTO(x,y) x=max(x,(__typeof__(x))y) #define FILL(x,y) memset(x,y,sizeof(x)) inline ll mult(ll a,ll b){ a%=MOD,b%=MOD; return (a*b)%MOD; } inline ll mypow(ll a,ll b){ if(b<=0) return 1; a%=MOD; ll res=1; while(b){ if(b&1) res=mult(res,a); a=mult(a,a); b>>=1; } return res; } char arr[maxn][maxn]; int dp[maxn][maxn][10][10]; vector<pii> v[maxn*maxn]; pii to[maxn][maxn][4]; int n,m; bool isin(int x,int y){ if(x<0 or x>=n or y<0 or y>=m) return false; return true; } int dx[4]={-1,0,1,0}; int dy[4]={0,1,0,-1}; int32_t main(){ ios::sync_with_stdio(false),cin.tie(0); int rob; cin>>rob>>n>>m; swap(n,m); REP(i,n) cin>>arr[i]; REP(i,n) REP(j,m) REP(a,rob) REP(b,rob) dp[i][j][a][b]=INF; REP(i,n){ REP(j,m){ if(isdigit(arr[i][j])){ int z=arr[i][j]-'0'-1; dp[i][j][z][z]=0; } } } REP(i,n){ REP(j,m){ if(arr[i][j]=='x') continue; REP(k,4){ int dir=k; if(arr[i][j]=='A') dir+=3; if(arr[i][j]=='C') dir++; dir%=4; int x=i,y=j; while(true){ int nx=x+dx[dir],ny=y+dy[dir]; if(!isin(nx,ny) or arr[nx][ny]=='x') break; x=nx,y=ny; if(arr[x][y]=='A') dir+=3; if(arr[x][y]=='C') dir++; dir%=4; } to[i][j][k]={x,y}; //cout<<i<<' '<<j<<' '<<k<<' '<<x<<' '<<y<<'\n'; } } } // return 0; REP(i,rob){ REP(l,rob-i){ int r=i+l; REP(a,n){ REP(b,m){ if(arr[a][b]=='x') continue; for(int k=l;k<r;k++){ MNTO(dp[a][b][l][r],dp[a][b][l][k]+dp[a][b][k+1][r]); } if(dp[a][b][l][r]!=INF) v[dp[a][b][l][r]].pb({a,b}); } } REP(a,n*m){ for(auto x:v[a]){ //cout<<x.f<<' '<<x.s<<'\n'; if(dp[x.f][x.s][l][r]!=a) continue; REP(k,4){ pii z=to[x.f][x.s][k]; if(dp[z.f][z.s][l][r]>dp[x.f][x.s][l][r]+1){ dp[z.f][z.s][l][r]=dp[x.f][x.s][l][r]+1; v[dp[z.f][z.s][l][r]].pb(z); } } } v[a].clear(); v[a].shrink_to_fit(); } } } int ans=INF; REP(i,n) REP(j,m) MNTO(ans,dp[i][j][0][rob-1]); if(ans==INF) ans=-1; 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...