#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/rope>
#define ll long long
#define pb push_back
#define sz(x) (int)(x).size()
#define mp make_pair
#define f first
#define s second
#define all(x) x.begin(), x.end()
using namespace std;
using namespace __gnu_pbds;
using namespace __gnu_cxx;
template<class T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>; ///find_by_order(),order_of_key()
template<class T1, class T2> ostream& operator<<(ostream& os, const pair<T1,T2>& a) { os << '{' << a.f << ", " << a.s << '}'; return os; }
template<class T> ostream& operator<<(ostream& os, const vector<T>& a){os << '{';for(int i=0;i<sz(a);i++){if(i>0&&i<sz(a))os << ", ";os << a[i];}os<<'}';return os;}
template<class T> ostream& operator<<(ostream& os, const set<T>& a) {os << '{';int i=0;for(auto p:a){if(i>0&&i<sz(a))os << ", ";os << p;i++;}os << '}';return os;}
template<class T> ostream& operator<<(ostream& os, const multiset<T>& a) {os << '{';int i=0;for(auto p:a){if(i>0&&i<sz(a))os << ", ";os << p;i++;}os << '}';return os;}
template<class T1,class T2> ostream& operator<<(ostream& os, const map<T1,T2>& a) {os << '{';int i=0;for(auto p:a){if(i>0&&i<sz(a))os << ", ";os << p;i++;}os << '}';return os;}
const int N=9;
const int H=500;
const int maxDist=H*H/5;
int n,h,w;
vector<int> dx={-1,0,1,0},dy={0,1,0,-1};
pair<int,int> dest[H][H][4],null={-1,-1};
vector<string> board;
bool end(int i,int j)
{
return i<0||i>=h||j<0||j>=w||board[i][j]=='x';
}
void sub(int &a,int b)
{
a-=b;
if(a<0)
a+=4;
}
void add(int &a,int b)
{
a+=b;
if(a>=4)
a-=4;
}
pair<int,int> dfs(int i,int j,int p)
{
int pp=p;
if(dest[i][j][p]!=null)
return dest[i][j][p];
if(end(i,j))
return dest[i][j][p]=make_pair(i,j);
if(board[i][j]=='A')
sub(p,1);
if(board[i][j]=='C')
add(p,1);
i+=dx[p];
j+=dy[p];
if(end(i,j))
return dest[i-dx[p]][j-dy[p]][pp]=make_pair(i-dx[p],j-dy[p]);
return dest[i-dx[p]][j-dy[p]][pp]=dfs(i,j,p);
}
vector<vector<vector<int> > > dp;
vector<vector<int> > initial_dp(H,vector<int>(H,(int)1e9));
int mask[H][H];
vector<pair<int,int> > q[maxDist];
void update(int k,int x,int y,int d)
{
if(d<dp[k][x][y])
{
dp[k][x][y]=d;
q[d].pb({x,y});
}
}
void bfs(int k)
{
for(int i=0;i<maxDist;i++)
for(auto p:q[i])
if(dp[k][p.f][p.s]>=i)
for(int l=0;l<4;l++)
update(k,dest[p.f][p.s][l].f,dest[p.f][p.s][l].s,i+1);
}
int main()
{
for(int i=0;i<H;i++)
for(int j=0;j<H;j++)
for(int k=0;k<4;k++)
dest[i][j][k]=null;
int t=(int)clock();
scanf("%i %i %i",&n,&h,&w);
swap(h,w);
board.resize(h);
for(int i=0;i<h;i++)
cin >> board[i];
for(int i=0;i<h;i++)
for(int j=0;j<w;j++)
for(int k=0;k<4;k++)
dfs(i,j,k);
vector<pair<int,int> > pos(n);
for(int i=0;i<h;i++)
for(int j=0;j<w;j++)
{
int t=board[i][j]-'0';
if(t>0&&t<10)
pos[t-1]=make_pair(i,j);
}
for(int i=0,k=0;i<n;i++)
{
for(int j=i;j>=0;j--,k++)
{
mask[j][i]=k;
dp.pb(initial_dp);
if(j==i)
update(k,pos[j].f,pos[j].s,0);
else
for(int x=0;x<h;x++)
for(int y=0;y<w;y++)
for(int l=j;l<i;l++)
update(k,x,y,dp[mask[j][l]][x][y]+dp[mask[l+1][i]][x][y]);
bfs(k);
for(int l=0;l<maxDist;l++)
q[l].clear();
}
}
int ans=1e9;
for(int x=0;x<h;x++)
for(int y=0;y<w;y++)
ans=min(ans,dp[mask[0][n-1]][x][y]);
if(ans==(int)1e9)
printf("-1\n");
else
printf("%i\n",ans);
return 0;
}
Compilation message
robots.cpp: In function 'int main()':
robots.cpp:90:9: warning: unused variable 't' [-Wunused-variable]
int t=(int)clock();
^
robots.cpp:91:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%i %i %i",&n,&h,&w);
~~~~~^~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
13 ms |
13304 KB |
Output is correct |
| 2 |
Correct |
13 ms |
13304 KB |
Output is correct |
| 3 |
Correct |
13 ms |
13304 KB |
Output is correct |
| 4 |
Correct |
13 ms |
13304 KB |
Output is correct |
| 5 |
Correct |
13 ms |
13304 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
13 ms |
13304 KB |
Output is correct |
| 2 |
Correct |
13 ms |
13304 KB |
Output is correct |
| 3 |
Correct |
13 ms |
13304 KB |
Output is correct |
| 4 |
Correct |
13 ms |
13304 KB |
Output is correct |
| 5 |
Correct |
13 ms |
13304 KB |
Output is correct |
| 6 |
Correct |
13 ms |
13304 KB |
Output is correct |
| 7 |
Correct |
12 ms |
13304 KB |
Output is correct |
| 8 |
Correct |
13 ms |
13304 KB |
Output is correct |
| 9 |
Correct |
13 ms |
13304 KB |
Output is correct |
| 10 |
Correct |
13 ms |
13304 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
13 ms |
13304 KB |
Output is correct |
| 2 |
Correct |
13 ms |
13304 KB |
Output is correct |
| 3 |
Correct |
13 ms |
13304 KB |
Output is correct |
| 4 |
Correct |
13 ms |
13304 KB |
Output is correct |
| 5 |
Correct |
13 ms |
13304 KB |
Output is correct |
| 6 |
Correct |
13 ms |
13304 KB |
Output is correct |
| 7 |
Correct |
12 ms |
13304 KB |
Output is correct |
| 8 |
Correct |
13 ms |
13304 KB |
Output is correct |
| 9 |
Correct |
13 ms |
13304 KB |
Output is correct |
| 10 |
Correct |
13 ms |
13304 KB |
Output is correct |
| 11 |
Runtime error |
112 ms |
68796 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 12 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
13 ms |
13304 KB |
Output is correct |
| 2 |
Correct |
13 ms |
13304 KB |
Output is correct |
| 3 |
Correct |
13 ms |
13304 KB |
Output is correct |
| 4 |
Correct |
13 ms |
13304 KB |
Output is correct |
| 5 |
Correct |
13 ms |
13304 KB |
Output is correct |
| 6 |
Correct |
13 ms |
13304 KB |
Output is correct |
| 7 |
Correct |
12 ms |
13304 KB |
Output is correct |
| 8 |
Correct |
13 ms |
13304 KB |
Output is correct |
| 9 |
Correct |
13 ms |
13304 KB |
Output is correct |
| 10 |
Correct |
13 ms |
13304 KB |
Output is correct |
| 11 |
Runtime error |
112 ms |
68796 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 12 |
Halted |
0 ms |
0 KB |
- |
