题解：P3638 [APIO2013] 机器人

· · 题解

不带任何 \log 的做法。

看到这种合并问题，显然直接区间 DP 啊。

我们直接设 dp_{l,r,i,j} 为机器人 l-r 在 (i,j) 停留的最小步数。

对于 l,r 这两维的转移可以直接区间 DP 在同一个格子合并。

对于每个点，预处理出把这个点的机器人分别往四个方向推能推到哪里。

对于 i,j 这两维可以对于同一个 l,r 直接 BFS 就可以（一个点可以转移到它能推到 4 个地方）。

那你说有多个起点初始值不同怎么办。

考虑 BFS 的过程：每次搜完同一层的并更新，再去搜下一层的。

于是我们直接对每个相同移动次数的起点存在一个数组里，因为每次合并最多移动一个机器人 wh 次，所以移动次数不超过 twh，可以开桶和 vector。

接着枚举每个距离，从相应距离的起点数组里取出可以转移的点和从队列头部取出相应距离的点就可以了。

于是每次广搜的时间复杂度就是 O(twh) 的（如果再存一个当前距离的最大值就远远达不到上界，但我就懒得去做了）。

然后就做完了。

时间复杂度 O(t^3wh)，具体看代码。

#include<bits/stdc++.h>
using namespace std;
int t,n,m;
char ch[510][510];
int dp[10][10][510][510];
int d[4][2]={{1,0},{0,-1},{-1,0},{0,1}};
int phx[510][510][4],phy[510][510][4];
struct node{
    int x,y,d;
}q[510*510];
bool vis[510][510];
vector<node>p[510*510*10];
int idx,num,head,tail;
inline bool operator < (node x,node y){
    return x.d<y.d;
}
inline void bfs(int l,int r){
    head=1,tail=0,idx=1,num=0;
    for(int D=0;D<=t*n*m;D++) p[D].clear();
    for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) vis[i][j]=0;
    for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) if(dp[l][r][i][j]<=t*n*m)
        p[dp[l][r][i][j]].push_back((node){i,j,dp[l][r][i][j]});
    for(int D=0;D<=t*n*m;D++){//枚举最短路长度 
        for(int j=0;j<p[D].size();j++){
            int x=p[D][j].x,y=p[D][j].y;
            idx++;
            if(vis[x][y]) continue;
            vis[x][y]=1;
            for(int k=0;k<4;k++){
                int tx=phx[x][y][k],ty=phy[x][y][k];
                if(dp[l][r][tx][ty]>dp[l][r][x][y]+1)
                    dp[l][r][tx][ty]=dp[l][r][x][y]+1,q[++tail]=(node){tx,ty,dp[l][r][x][y]+1};
            }
        }
        while(head<=tail && q[head].d<=D){
            int x=q[head].x,y=q[head].y;
            head++;
            if(vis[x][y]) continue;
            vis[x][y]=1;
            for(int k=0;k<4;k++){
                int tx=phx[x][y][k],ty=phy[x][y][k];
                if(dp[l][r][tx][ty]>dp[l][r][x][y]+1)
                    dp[l][r][tx][ty]=dp[l][r][x][y]+1,q[++tail]=(node){tx,ty,dp[l][r][x][y]+1};
            }
        }
    }
}
signed main() {
    cin>>t>>m>>n;
    memset(dp,0x3f,sizeof dp);
    for(int i=1;i<=n;i++) for(int j=1;j<=m;j++){
        cin>>ch[i][j];
        if('1'<=ch[i][j] && ch[i][j]<='9') dp[ch[i][j]-'0'][ch[i][j]-'0'][i][j]=0,ch[i][j]='.';
    }
    for(int i=1;i<=n;i++) for(int j=1;j<=m;j++){
        if(ch[i][j]=='x') continue;
        for(int k=0;k<4;k++){
            int x=i,y=j,p=k;
            while(true){
                if(ch[x][y]=='A') p=(p+3)%4;
                if(ch[x][y]=='C') p=(p+1)%4;
                int tx=x+d[p][0],ty=y+d[p][1];
                if(tx<1 || ty<1 || tx>n || ty>m || ch[tx][ty]=='x') break;
                x=tx,y=ty;
            }
            phx[i][j][k]=x,phy[i][j][k]=y;
        }
    }
    for(int i=1;i<=t;i++) bfs(i,i);
    for(int k=2;k<=t;k++){
        for(int i=1;i+k-1<=t;i++){
            int j=i+k-1;
            for(int p=i;p<j;p++)
                for(int a=1;a<=n;a++) for(int b=1;b<=m;b++) dp[i][j][a][b]=min(dp[i][j][a][b],dp[i][p][a][b]+dp[p+1][j][a][b]);
            bfs(i,j);
        }
    }
    int ans=2e9;
    for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) ans=min(ans,dp[1][t][i][j]);
    if(ans<=1e9) cout<<ans;
    else cout<<-1;
    return 0;
}