思路:
就是一堆机器人合并起来,看起来天然的生成树模型吗.
令\(f[i][j][x][y]\)表示区间\([i,j]\)的机器人合并到位置\((x,y)\)使得最小推动次数,模仿斯坦纳树,我们有以下两种转移:
\[f[i][j][x][y]=f[i][j][x'][y']+1\]
\[f[i][j][x][y]=f[i][k][x][y]+f[k+1][j][x][y]\]
第二种转移直接暴力即可.
对于第一种转移,我们则可以利用一次最短路spfa求解.
至于如何构图呢?我们需要预处理出对于机器人目前在的每一个位置,我们将机器人推动一个方向后最终处于的位置.
我煞笔被坑了几次:首先机器人最终是可以停在转动器位置的.
如果我们每次暴力枚举,会T,因此只能利用记忆化搜索来做.
反正这个预处理坑了我好久.(太弱不解释
可是只有这些优化还是不能AC的!
我们每次暴力spfa的耗时还是过长了.
这怎么优化?
我们发现边权都是1,下面介绍一种神奇的方法:
我们维护两个队列,首先将所有的点按照距离从小到大的顺序加入第二个队列中,随后进行松弛,每次选择两个队列队头距离比较小的点取出进行松弛,并将松弛后的点加入第一个队列中,这样就起到了优先队列的作用,且不用带一个\(log\),这样做是线性的.
这样才能AC!
#include<cstdio>
#include<cstring>
#include<cctype>
#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;
#define INF 0x1f1f1f1f
#define N 10
#define W 510
#define H 510
int n,w,h;
char s[W][H];
int f[N][N][W][H],tclock,vis[W][H][4];
int nowi,nowj;
struct Ins{
short x,y;
Ins(){}
Ins(int _x,int _y):x(_x),y(_y){}
bool operator<(const Ins&B)const{return f[nowi][nowj][x][y]<f[nowi][nowj][B.x][B.y];}
}vec[W][H][4];
const int dx[]={-1,0,1,0},dy[]={0,-1,0,1};
queue<Ins>q1,q2;
Ins seq[W*H],tmp[W*H];int siz,rk[W*H],t[200010],cnt[200010];
inline void add(int x,int c,int v){if(t[x]!=v)t[x]=v,cnt[x]=0;cnt[x]+=c;}
inline int ask(int x,int v){if(t[x]!=v)t[x]=v,cnt[x]=0;return cnt[x];}
int sig;
inline void Rdxsort(){
++sig;
int Max=0;register int i;int x,y;
for(i=1;i<=siz;++i)add(f[nowi][nowj][x=seq[i].x][y=seq[i].y],1,sig),Max=max(Max,f[nowi][nowj][x][y]);
for(i=1;i<=Max;++i)add(i,ask(i-1,sig),sig);
for(i=1;i<=siz;++i)rk[i]=ask(f[nowi][nowj][x=seq[i].x][y=seq[i].y],sig),add(f[nowi][nowj][x][y],-1,sig),tmp[rk[i]]=seq[i];
for(i=1;i<=siz;++i)seq[i]=tmp[i];
}
bool inq[W][H];
inline void work(){
register int i,j,k;
for(i=1;i<=siz;++i)q2.push(seq[i]),inq[seq[i].x][seq[i].y]=1;
Ins t,to;int d1,d2;
while(!q1.empty()||!q2.empty()){
if(q1.empty())t=q2.front(),q2.pop();
else if(q2.empty())t=q1.front(),q1.pop();
else{
d1=f[nowi][nowj][q1.front().x][q1.front().y];
d2=f[nowi][nowj][q2.front().x][q2.front().y];
if(d1<d2)t=q1.front(),q1.pop();else t=q2.front(),q2.pop();
}
for(inq[t.x][t.y]=k=0;k<4;++k){
if((to=vec[t.x][t.y][k]).x!=INF&&f[nowi][nowj][to.x][to.y]>f[nowi][nowj][t.x][t.y]+1){
f[nowi][nowj][to.x][to.y]=f[nowi][nowj][t.x][t.y]+1;
if(!inq[to.x][to.y])inq[to.x][to.y]=1,q1.push(to);
}
}
}
}
Ins calc(int x,int y,int v){
if(vis[x][y][v]==tclock)return Ins(-1,-1);vis[x][y][v]=tclock;
if(!(vec[x][y][v].x==0&&vec[x][y][v].y==0))return vec[x][y][v];
int nowv=v;if(s[x][y]=='A')nowv=(v+1)%4;if(s[x][y]=='C')nowv=(v+3)%4;
int tx=x+dx[nowv],ty=y+dy[nowv];
if(s[tx][ty]=='x')return vec[x][y][v]=Ins(x,y);
return vec[x][y][v]=calc(tx,ty,nowv);
}
int main(){
scanf("%d%d%d",&n,&h,&w);
register int i,j,k,p,q;
for(i=1;i<=w;++i)scanf("%s",s[i]+1);
memset(f,0x1f,sizeof f);
int id;
for(i=1;i<=w;++i)for(j=1;j<=h;++j)if(s[i][j]>='1'&&s[i][j]<='9')id=s[i][j]-'0',f[id][id][i][j]=0;
for(i=0;i<=w+1;++i)s[i][0]=s[i][h+1]='x';
for(j=0;j<=h+1;++j)s[0][j]=s[w+1][j]='x';
for(i=1;i<=w;++i)for(j=1;j<=h;++j)if(s[i][j]!='x')
for(k=0;k<4;++k)
++tclock,vec[i][j][k]=calc(i,j,k);
for(int l=1;l<=n;++l)for(i=1;i+l-1<=n;++i){
j=i+l-1;
for(k=i;k<j;++k)for(p=1;p<=w;++p)for(q=1;q<=h;++q)f[i][j][p][q]=min(f[i][j][p][q],f[i][k][p][q]+f[k+1][j][p][q]);
siz=0;for(p=1;p<=w;++p)for(q=1;q<=h;++q)if(f[i][j][p][q]!=INF)seq[++siz]=Ins(p,q);
nowi=i,nowj=j,Rdxsort();
work();
}
int ans=INF;
for(i=1;i<=w;++i)for(j=1;j<=h;++j)ans=min(ans,f[1][n][i][j]);
if(ans==INF)puts("-1");else printf("%d\n",ans);
return 0;
}