题解 P1139【单向双轨道】

Utilokasteinn · 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;
}