自动搬运

查看原文

来自洛谷，原作者为

	Utilokasteinn 技不如人

搬运于2025-08-24 21:21:24，当前版本为作者最后更新于2021-02-26 20:27:25，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

一道挺好的搜索题，剪枝也很简单。

采用迭代加深搜索，因为每辆火车至少要做 $1$ 次调度，最多要做 $3$ 次调度。所以枚举调度次数从 $n$ 到 $3n$ 即可。如果没有答案则输出“NO”。

每次调度，看看可不可以从这个位置调度到后面的位置，有的话即调度。

几个剪枝：

• 因为一辆火车到出口就不能往回，所以答案就一定了。每次深搜时判断是否符合标准，否则直接退出。

• 如果剩余的调度步数小于还没到出口的火车数，即可以直接退出。

• 如果当前这个位置没火车即不用搜了。

代码如下，比其他题解都简洁非常多：

#include<bits/stdc++.h>
using namespace std;
int n,mb[30],ans[30],from[100],to[101],s[4][30],cnt[4],lim;
char ss[30];
void dfs(int step)
{
    if(s[3][cnt[3]]!=mb[cnt[3]])return;
    if(lim-step+1<cnt[0]+cnt[1]+cnt[2])return;
    if(step==lim+1&&!cnt[0]+cnt[1]+cnt[2])
	{
        for(int i=1;i<step;i++)
			printf("%c %c %c\n",ans[i]+'a'-1,from[i]+'A',to[i]+'A');
        exit(0);
    }
    if(step>lim)return;
	for(int i=0;i<=2;i++)
		for(int j=i+1;j<=3&&cnt[i];j++)
		{
			int flag=s[i][cnt[i]--];
			ans[step]=s[j][++cnt[j]]=flag;
			from[step]=i,to[step]=j;
			dfs(step+1);
			s[i][++cnt[i]]=flag,cnt[j]--;	
		}
}
int main()
{
    scanf("%d%s",&n,ss+1);
    for(int i=1;i<=n;i++)
		mb[n-i+1]=ss[i]-'a'+1,s[0][++cnt[0]]=i;
    for(lim=n;lim<=3*n;lim++)
		dfs(1);
    printf("NO");
    return 0;
}