#include <iostream>
#include <algorithm>
#include <string.h>
#include <queue>
using namespace std;
#define itn int
pair<short,short>lastp[501][501][4];
int dp[45][501][501];
char arr[501][501];
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');
}
int ge(int n,int m)
{
int ans=m-n;
int i;
for(i=0;i<n;i++)
ans+=n-i;
return ans;
}
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++;
c+=4;
c%=4;
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<short,short>>co[300100];
int vis[501][501];
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[ge(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[ge(s,e)][l][m]=min((int)dp[ge(s,e)][l][m],dp[ge(s,k)][l][m]+dp[ge(k+1,e)][l][m]);
if(i==K-1)
ans=min(ans,(int)dp[ge(s,e)][l][m]);
}
}
}
for(l=0;l<N;l++)
{
for(m=0;m<M;m++)
{
if(dp[ge(s,e)][l][m]<=N*M)
co[dp[ge(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[ge(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
robots.cpp: In function 'int main()':
robots.cpp:113:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<short int, short int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
113 | for(l=0;l<co[k].size();l++)
| ~^~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
29 ms |
56452 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
29 ms |
56452 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
29 ms |
56452 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
29 ms |
56452 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
