#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;
cout<<c[i]+1<<'\n';
}
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],G[l][r][i][j]+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;
return 0;
}
Compilation message
robots.cpp: In function 'int main()':
robots.cpp:58:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
58 | cin>>c[i]+1;
| ~~~~^~
robots.cpp:106:10: warning: unused variable 'x' [-Wunused-variable]
106 | int x=Tmp.back().x;
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
63 ms |
142792 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
63 ms |
142792 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
63 ms |
142792 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
63 ms |
142792 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
