#include<algorithm>
#include<vector>
#include<iostream>
#include<string>
#include<cstring>
#include<cstdio>
#include<queue>
#define fr first
#define sc second
#define mp make_pair
#define pb push_back
#define REP(i,m) for(int i=0;i<(int)m;++i)
#define REPN(i,m,in) for(int i=in;i<(int)m;++i)
#define ALL(t) (t).begin(),(t).end()
#define dump(x) cerr<<#x<<" = "<<x<<endl
#define prl cerr<<"LINE "<<__LINE__<<" is called"<<endl
using namespace std;
template<class T> void debug(T a,T b){ for(;a!=b;++a) cerr<<*a<<' '; cerr<<endl ; }
typedef pair<int,int> pi;
typedef long long int lint;
const int INF=510000000;
char buf[505][505];
int dp[50][505][505];
pi g[505][505][4];
bool vis[505][505][4];
int n,w,h;
int dx[]={0,1,0,-1},dy[]={1,0,-1,0};
pi rec(int y,int x,int d){
pi& res=g[y][x][d];
if(res.fr!=-1) return res;
if(vis[y][x][d]) return res=mp(-2,-2);
vis[y][x][d]=1;
if(buf[y][x]=='A') d=(d+1)%4;
if(buf[y][x]=='C') d=(d+3)%4;
int px=x+dx[d],py=y+dy[d];
if(px<0 || py<0 || px>=w || py>=h || buf[py][px]=='x'){
return res=mp(y,x);
}
return res=rec(py,px,d);
}
pi pos[10];
int hash[10][10];
void prep(int sy,int sx,int id){
queue<pi> q;
dp[hash[id][id+1]][sy][sx]=0;
q.push(mp(sy,sx));
while(!q.empty()){
pi cur=q.front();q.pop();
REP(d,4){
pi to=g[cur.fr][cur.sc][d];
if(to.fr==-2) continue;
if(dp[hash[id][id+1]][to.fr][to.sc]!=-1) continue;
dp[hash[id][id+1]][to.fr][to.sc]=dp[hash[id][id+1]][cur.fr][cur.sc]+1;
q.push(to);
}
}
REP(i,h) REP(j,w) if(dp[hash[id][id+1]][i][j]==-1) dp[hash[id][id+1]][i][j]=INF;
}
vector<pi> posByCost[500*501*10];
vector<int> used;
int main(){
int cntt=0;
REP(i,9) REPN(j,10,i+1) hash[i][j]=cntt++;
scanf("%d%d%d",&n,&w,&h);
REP(i,h) scanf("%s",buf[i]);
REP(i,h) REP(j,w){
if(buf[i][j]>='1' && buf[i][j]<='9'){
pos[buf[i][j]-'1']=mp(i,j);
}
}
memset(g,-1,sizeof(g));
REP(i,h) REP(j,w) REP(d,4) rec(i,j,d);
memset(dp,-1,sizeof(dp));
REP(i,n){
prep(pos[i].fr,pos[i].sc,i);
}
queue<pi> q;
for(int len=2;len<=n;++len) REP(i,n-len+1){
int j=i+len;
pair<int,pi> mini;mini.fr=INF;
REP(y,h) REP(x,w){
dp[hash[i][j]][y][x]=INF;
REP(k,len-1){
int div=i+k+1;
dp[hash[i][j]][y][x]=min(dp[hash[i][j]][y][x],dp[hash[i][div]][y][x]+dp[hash[div][j]][y][x]);
}
if(dp[hash[i][j]][y][x]!=INF){
used.pb(dp[hash[i][j]][y][x]);
posByCost[dp[hash[i][j]][y][x]].pb(mp(y,x));
mini=min(mini,mp(dp[hash[i][j]][y][x],mp(y,x)));
}
}
if(mini.fr==INF) continue;
REP(k,posByCost[mini.fr].size()) q.push(posByCost[mini.fr][k]);
posByCost[mini.fr].clear();
while(!q.empty()){
pi p=q.front();q.pop();
int c=dp[hash[i][j]][p.fr][p.sc];
if(!posByCost[c+1].empty()){
REP(k,posByCost[c+1].size()){
pi p2=posByCost[c+1][k];
if(dp[hash[i][j]][p2.fr][p2.sc]<c+1) continue;
q.push(p2);
}
posByCost[c+1].clear();
}
REP(d,4){
pi nxt=g[p.fr][p.sc][d];
if(nxt.fr==-2 || dp[hash[i][j]][nxt.fr][nxt.sc]<=c+1) continue;
dp[hash[i][j]][nxt.fr][nxt.sc]=c+1;
q.push(nxt);
}
}
REP(k,used.size()) posByCost[used[k]].clear();
used.clear();
}
int res=INF;
REP(i,h) REP(j,w) res=min(res,dp[hash[0][n]][i][j]);
if(res==INF) res=-1;
printf("%d\n",res);
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
24 ms |
119416 KB |
Output is correct |
| 2 |
Correct |
16 ms |
119416 KB |
Output is correct |
| 3 |
Correct |
24 ms |
119416 KB |
Output is correct |
| 4 |
Correct |
32 ms |
119416 KB |
Output is correct |
| 5 |
Correct |
24 ms |
119416 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
24 ms |
119416 KB |
Output is correct |
| 2 |
Correct |
24 ms |
119416 KB |
Output is correct |
| 3 |
Correct |
28 ms |
119416 KB |
Output is correct |
| 4 |
Correct |
36 ms |
119416 KB |
Output is correct |
| 5 |
Correct |
28 ms |
119416 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
136 ms |
123056 KB |
Output is correct |
| 2 |
Correct |
36 ms |
119416 KB |
Output is correct |
| 3 |
Correct |
64 ms |
119416 KB |
Output is correct |
| 4 |
Correct |
216 ms |
125352 KB |
Output is correct |
| 5 |
Correct |
96 ms |
120496 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
212 ms |
119416 KB |
Output is correct |
| 2 |
Correct |
584 ms |
139204 KB |
Output is correct |
| 3 |
Correct |
252 ms |
123096 KB |
Output is correct |
| 4 |
Correct |
216 ms |
119416 KB |
Output is correct |
| 5 |
Correct |
420 ms |
134636 KB |
Output is correct |
