This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
///~~~LOTA~~~///
#include <bits/stdc++.h>
using namespace std;
#define nl '\n'
#define ff first
#define ss second
#define ll long long
#define append push_back
#define pii pair<int,int>
#define all(x) (x).begin(),(x).end()
#define N 502
#define M 10
int n,m,o;
char c[N][N];
vector<pii> a[N][N];
int dist[N][N][M][M];
void mark(int x,int y,int p,int q,int r,int s){
if(!x || x>n || !y || y>m) return;
if(c[x][y]=='x'){
p=x+r;
q=y+s;
}
else if(p!=x || q!=y)
a[x][y].append({p,q});
if(c[x][y]=='C'){
swap(r,s);
r=-r;
}
if(c[x][y]=='A'){
swap(r,s);
s=-s;
}
mark(x+r,y+s,p,q,r,s);
}
void dijkstra(int l,int r){
int d,p,q;
priority_queue<pair<int,pii>,vector<pair<int,pii>>,greater<pair<int,pii>>> Q;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
if(dist[i][j][l][r]<1e8)
Q.push({dist[i][j][l][r],{i,j}});
while(!Q.empty()){
d=Q.top().ff;
p=Q.top().ss.ff;
q=Q.top().ss.ss;
Q.pop();
if(d==dist[p][q][l][r]){
for(auto& i:a[p][q]){
if(d+1<dist[i.ff][i.ss][l][r]){
dist[i.ff][i.ss][l][r]=d+1;
Q.push({d+1,i});
}
}
}
}
}
void solve(){
int s;
cin>>o>>m>>n;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
cin>>c[i][j];
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
for(int l=1;l<=o;l++)
for(int r=l;r<=o;r++)
dist[i][j][l][r]=1e8;
for(int i=1;i<=n;i++){
mark(i,1,i,1,0,1);
mark(i,m,i,m,0,-1);
}
for(int i=1;i<=m;i++){
mark(1,i,1,i,1,0);
mark(n,i,n,i,-1,0);
}
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
s=c[i][j]-'0';
if(s>0 && s<10){
dist[i][j][s][s]=0;
dijkstra(s,s);
}
}
}
for(int j=1;j<o;j++){
for(int i=1;i+j<=o;i++){
for(int p=1;p<=n;p++)
for(int q=1;q<=m;q++)
for(int d=i;d<i+j;d++)
dist[p][q][i][i+j]=min(dist[p][q][i][i+j]
,dist[p][q][i][d]+dist[p][q][d+1][i+j]);
dijkstra(i,i+j);
}
}
s=1e8;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
s=min(s,dist[i][j][1][o]);
if(s==1e8) s=-1;
cout<<s;
}
int main(){
ios_base::sync_with_stdio(false);cin.tie(NULL);
solve();
return 0;
}
# | 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... |