思路:

就是一堆机器人合并起来,看起来天然的生成树模型吗.

令\(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;
}

思路:

斯坦纳树裸题.

输出方案的话记录一下转移就好了.

#include<cstdio>
#include<cstring>
#include<cctype>
#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;
 
#define INF 0x1f1f1f1f
 
#define N 11
#define M 11
int n,m,d[N][M],lab[N][M],cnt;
 
int f[N][M][1<<11];
 
struct Lastans{
    int x,y,S;
    Lastans(){}
    Lastans(int _x,int _y,int _S):x(_x),y(_y),S(_S){}
}g[N][M][1<<11];
 
struct Ins{
    int x,y;
    Ins(){}
    Ins(int _x,int _y):x(_x),y(_y){}
};
queue<Ins>q;
 
const int dx[]={-1,1,0,0},dy[]={0,0,1,-1};
bool inq[N][M];
#define Inrange(x,l,r) ((x)>=(l)&&(x)<=(r))
inline void spfa(int S){
    int tx,ty,i,j;
    while(!q.empty()){
        Ins t=q.front();q.pop();inq[i=t.x][j=t.y]=0;
        for(int k=0;k<4;++k)if(Inrange(tx=i+dx[k],1,n)&&Inrange(ty=j+dy[k],1,m)){
            if(f[tx][ty][S]>f[i][j][S]+d[tx][ty]){
                f[tx][ty][S]=f[i][j][S]+d[tx][ty],g[tx][ty][S]=Lastans(i,j,S);
                if(!inq[tx][ty])inq[tx][ty]=1,q.push(Ins(tx,ty));
            }
        }
    }
}
 
bool vis[N][M];
inline void dfs(int x,int y,int S){
    if(!S)return;
    vis[x][y]=1;if((!d[x][y])&&(S==(1<<lab[x][y])))return;
    Lastans p=g[x][y][S];
    dfs(p.x,p.y,p.S);
    if(S!=p.S)dfs(x,y,S-p.S);
}
 
int main(){
    scanf("%d%d",&n,&m);
    register int i,j;for(i=1;i<=n;++i)for(j=1;j<=m;++j){scanf("%d",&d[i][j]);if(!d[i][j])lab[i][j]=cnt++;}
    memset(f,0x1f,sizeof f);
    for(i=1;i<=n;++i)for(j=1;j<=m;++j)if(!d[i][j])f[i][j][1<<lab[i][j]]=0;
    for(int S=1;S<(1<<cnt);++S){
        for(int mas=(S-1)&S;mas;mas=(mas-1)&S)
            for(i=1;i<=n;++i)
                for(j=1;j<=m;++j)
                    if(f[i][j][S]>f[i][j][mas]+f[i][j][S-mas]-d[i][j])
                        f[i][j][S]=f[i][j][mas]+f[i][j][S-mas]-d[i][j],g[i][j][S]=Lastans(i,j,mas);
        memset(inq,0,sizeof inq);
        for(i=1;i<=n;++i)for(j=1;j<=m;++j)if(f[i][j][S]!=INF)q.push(Ins(i,j)),inq[i][j]=1;
        spfa(S);
    }
 
    Lastans res;
    int ans=INF;for(i=1;i<=n;++i)for(j=1;j<=m;++j)if(ans>f[i][j][(1<<cnt)-1])ans=f[i][j][(1<<cnt)-1],res=Lastans(i,j,(1<<cnt)-1);
    printf("%d\n",ans);
    dfs(res.x,res.y,(1<<cnt)-1);
    for(i=1;i<=n;++i){
        for(j=1;j<=m;++j)if(!vis[i][j])putchar('_');else if(vis[i][j]&&d[i][j]==0)putchar('x');else putchar('o');puts("");
    }
    return 0;
}