This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <iostream>
#include <algorithm>
#include <string.h>
#include <queue>
using namespace std;
#define itn int
pair<int,int>lastp[401][401][4];
int dp[9][9][401][401];
char arr[401][401];
int dx[4]={-1,0,1,0};
int dy[4]={0,1,0,-1};
int N,M,K;
int isv(int n,int m)
{
return (n<0)||(n>=N)||(m<0)||(m>=M)||(arr[n][m]=='x');
}
pair<int,int> findne(int n,int m,int c)
{
if(lastp[n][m][c].first!=-1)
return lastp[n][m][c];
lastp[n][m][c]={-2,-2};
if(isv(n,m))
{
return lastp[n][m][c];
}
int on=n;
int om=m;
int oc=c;
if(arr[n][m]=='A')
c--;
if(arr[n][m]=='C')
c++;
n+=dx[c];
m+=dy[c];
if(isv(n,m))
{
return lastp[on][om][oc]={on,om};
}
return lastp[on][om][oc]=findne(n,m,c);
}
vector<pair<int,int>>co[200100];
int vis[401][401];
int main()
{
memset(lastp,-1,sizeof(lastp));
memset(dp,1,sizeof(dp));
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> K >> M >>N;
int i,j,k,l,m;
for(i=0;i<N;i++)
{
cin >> arr[i];
}
for(i=0;i<N;i++)
{
for(j=0;j<M;j++)
{
if(arr[i][j]>='0'&&arr[i][j]<='9')
{
dp[arr[i][j]-'1'][arr[i][j]-'1'][i][j]=0;
}
for(k=0;k<4;k++)
findne(i,j,k);
}
}
int ans=123456789;
for(i=0;i<K;i++)
{
int j;
for(j=0;j<K-i;j++)
{
memset(vis,0,sizeof(vis));
int s=j;
int e=j+i;
for(k=0;k<=N*M;k++)
{
co[k].clear();
}
for(k=s;k<e;k++)
{
for(l=0;l<N;l++)
{
for(m=0;m<M;m++)
{
dp[s][e][l][m]=min(dp[s][e][l][m],dp[s][k][l][m]+dp[k+1][e][l][m]);
if(i==K-1)
ans=min(ans,dp[s][e][l][m]);
}
}
}
for(l=0;l<N;l++)
{
for(m=0;m<M;m++)
{
if(dp[s][e][l][m]<=N*M)
co[dp[s][e][l][m]].push_back({l,m});
}
}
for(k=0;k<=N*M;k++)
{
int l;
for(l=0;l<co[k].size();l++)
{
if(co[k][l].first<0||vis[co[k][l].first][co[k][l].second])
continue;
dp[s][e][co[k][l].first][co[k][l].second]=k;
if(i==K-1)
ans=min(ans,k);
vis[co[k][l].first][co[k][l].second]=1;
for(m=0;m<4;m++)
{
co[k+1].push_back(lastp[co[k][l].first][co[k][l].second][m]);
}
}
}
}
}
if(ans>N*M)
cout <<-1;
else
cout << ans;
}
Compilation message (stderr)
robots.cpp: In function 'int main()':
robots.cpp:103:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
103 | for(l=0;l<co[k].size();l++)
| ~^~~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |