思路:
就是一堆机器人合并起来,看起来天然的生成树模型吗.
令\(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; }