自动搬运

查看原文

来自洛谷，原作者为

	shadowice1984 これが勘違いでも、これが勘違いでも

搬运于2025-08-24 21:51:04，当前版本为作者最后更新于2018-12-16 11:27:19，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

我也不知道为什么随手写了一下就抢了这题的rk1……

拒绝stl的队列从我做起

为了方便起见我们认为$(-1,0),(0,1),(1,0),(0,-1)$这四个方向的标号分别为$0,1,2,3$

首先我们设$dp(i,j,k)$ 表示在$i,j$点按照k这个方向踹一脚机器人这个机器人会跑到什么地方去

那么这个东西还是比较好转移的，直接递归下去记忆化搜索就可以了

但是我们可能需要注意两个点，第一点就是如果$(i+dx(k),j+dy(k))$这个点是墙或者障碍物的话我们需要将$dp(i,j,k)$设为$num(i,j)$意思就是说这个机器人不会动了

另外一点就是环，我们在记忆化搜索的时候记录一下什么状态被压在了栈里，如果我们发现我们访问了一个栈内的元素,那么将这个栈内的元素的dp值置为$-1$，注意这里一定要和墙的标号区别开，不然会导致一些奇奇怪怪的错误

好了那么假设我们处理出了这个dp数组，现在我们就可以建出一张图来了~

然后我们发现这个问题十分的像斯坦纳树问题，只是我们不是状压dp而是区间dp了

具体点来讲我们设$dp(i,j,k)$表示$(i,j)$这个复合机器人出现在$k$点的最小代价

那么层外转移就是向区间dp一样的枚举分割点mid进行转移

$$dp(i,j,k)=\min_{mid=l}^{r-1}(dp(i,mid,k)+dp(mid+1,r,k)) $$

然后层内的转移我们发现似乎满足三角不等式(其中$k.alist$表示点k的出边集合)

$$dp(i,j,k) \leq min_{v\in k.alist}dp(i,j,v)+1$$

不过此时似乎转移是带环的……

那么一般斯坦树的套路就是用spfa进行转移……

不过这里不知道为什么spfa会tle，所以我们需要一些比较nb一点的剪枝，不然过不去

具体点来讲我们开两个队列，一个存一开始的点，并且这个队列中点是排好序的，排序这里建议手写计数排序，会快一点，另一个队列存需要去松弛别的点的点

然后每次取队头的时候去两个点中dis值较小的那个去松弛，加上这个玄学剪枝之后我们的spfa就跑的飞起了，然后就不用担心tle了~

然后这题并没有你想的那么毒瘤，注意实现方式的话还是很好写的~

上代码~

// luogu-judger-enable-o2
#include<cstdio>
#include<algorithm>
using namespace std;const int N=520;const int E=4*1e6+10;const int M=12;
int dx[4]={-1,0,1,0};int dy[4]={0,1,0,-1};
bool book[N][N][4];int dp[N][N][4];int tr[N][N];int ctt;int n;int w;int h;
int v[4*N*N];int x[4*N*N];int ct;int al[N*N];char mp[N][N];
inline void add(int u,int V){v[++ct]=V;x[ct]=al[u];al[u]=ct;}
inline int dfs(const int& x,const int& y,const int& tw)//记忆化搜索
{
    if(book[x][y][tw]){return dp[x][y][tw]=-1;}
    if(dp[x][y][tw]!=-2)return dp[x][y][tw];
    book[x][y][tw]=true;int tx=x+dx[tw];int ty=y+dy[tw];
    switch(mp[tx][ty])
    {
        case 'x':{dp[x][y][tw]=tr[x][y];break;}
        case 'A':{dp[x][y][tw]=dfs(tx,ty,(tw+3)%4);break;}
        case 'C':{dp[x][y][tw]=dfs(tx,ty,(tw+1)%4);break;}
        default:{dp[x][y][tw]=dfs(tx,ty,tw);break;}
    }book[x][y][tw]=false;return dp[x][y][tw];
}int sum[N*N];int q1[N*N];int q2[E];bool inq[N*N];int hd;int tl;int dis[M][M][N*N];
inline void rixs(int* dis)//计数排序
{
    int mx=0;for(int i=1;i<=ctt;i++)if(dis[i]<0x3f3f3f3f)mx=max(mx,dis[i]);
    for(int i=1;i<=ctt;i++)if(dis[i]<0x3f3f3f3f)sum[dis[i]]++;
    for(int i=1;i<=mx;i++)sum[i]+=sum[i-1];
    for(int i=ctt;i>=1;i--)if(dis[i]<0x3f3f3f3f)q1[sum[dis[i]]--]=i;
    for(int i=1;i<=ctt;i++)if(dis[i]<0x3f3f3f3f)inq[i]=true;
    for(int i=0;i<=mx;i++)sum[i]=0;
}
inline void ex_spfa(int* dis)//spfa
{
    rixs(dis);int cur=1;int hd=1;int tl=0;
    while((cur<=ctt)||(hd<=tl))
    {
        int nw=0x3f3f3f3f;
        if((cur<=ctt)&&(hd>tl||dis[q1[cur]]<=dis[q2[hd]]))nw=q1[cur],cur++;
        else nw=q2[hd],hd++;inq[nw]=false;
        for(int i=al[nw];i;i=x[i])
            if(dis[v[i]]>dis[nw]+1){dis[v[i]]=dis[nw]+1;if(!inq[v[i]])inq[v[i]]=true,q2[++tl]=v[i];}
    }
}
int main()
{
    scanf("%d%d%d",&n,&w,&h);
    for(int i=1;i<=h;i++)scanf("%s",mp[i]+1);
    for(int i=1;i<=h;i++)//各种初始化~
        for(int j=1;j<=w;j++)if(mp[i][j]!='x')tr[i][j]=++ctt;
    for(int j=0;j<=w+1;j++)mp[0][j]='x';for(int j=0;j<=w+1;j++)mp[h+1][j]='x';
    for(int i=0;i<=h+1;i++)mp[i][0]='x';for(int i=0;i<=h+1;i++)mp[i][w+1]='x';
    for(int i=1;i<=h;i++)
        for(int j=1;j<=w;j++)for(int k=0;k<4;k++)dp[i][j][k]=-2;
    for(int i=1;i<=h;i++)
        for(int j=1;j<=w;j++)if(mp[i][j]!='x')for(int k=0;k<4;k++)dfs(i,j,k);
    for(int i=1;i<=h;i++)
        for(int j=1;j<=w;j++)
            if(mp[i][j]!='x')for(int k=0;k<4;k++)
                if(dp[i][j][k]!=-1&&dp[i][j][k]!=tr[i][j])add(tr[i][j],dp[i][j][k]);
    for(int i=1;i<=n;i++)
        for(int j=i;j<=n;j++)for(int k=1;k<=ctt;k++)dis[i][j][k]=0x3f3f3f3f;
    for(int i=1;i<=h;i++)
        for(int j=1;j<=w;j++)
            if('0'<mp[i][j]&&mp[i][j]<='9'){int t=mp[i][j]-'0';dis[t][t][tr[i][j]]=0;}
    for(int len=1;len<=n;len++)
        for(int l=1,r=l+len-1;r<=n;l++,r++)//dp
        {
            for(int mid=l;mid<r;mid++)
                for(int k=1;k<=ctt;k++)dis[l][r][k]=min(dis[l][r][k],dis[l][mid][k]+dis[mid+1][r][k]);
            ex_spfa(dis[l][r]);
        }int ans=0x3f3f3f3f;
    for(int i=1;i<=ctt;i++)ans=min(ans,dis[1][n][i]);printf("%d",(ans==0x3f3f3f3f)?-1:ans);//拜拜程序~
}