P1139 单向双轨道

题目地址

一道深搜的题目 2个点卡了我好久
第一个点就是结果有很多种
必须要最优结果 长度最短 字典顺序最小
第二个点就是超时 要剪枝

首先移动步数最小肯定是n 最大是3n 每个字母移动3次
从最小的操作步数n开始按照字典顺序搜索
找到答案了直接返回 肯定是最优结果
如果搜索完成还没找到结果 就是无解

剪枝:当前剩余的步数小于需要进站的字母时候 直接回溯

#include <stdio.h>

const int Width=4;
const int MaxMoveType=6;
const int EndIndex=3;
const int MaxLen=27;
const int MaxStep=90;

//无限长度的栈 必须要用链表实现
struct Stack
{
    int data[MaxStep][3];
    int size;//队列元素个数
};

Stack* newStack(){
    Stack* stack=new Stack;
    stack->size=0;
    return stack;
}

//入栈
void pushStack(Stack* s,int* step)
{
    s->data[s->size][0]=step[0];
    s->data[s->size][1]=step[1];
    s->data[s->size][2]=step[2];
    s->size++;
}

//出栈
int popStack(Stack* s){
    if(s->size==0)
    {
        return 0;
    }
    else{
        s->size--;
        return 1;
    }
}

//栈元素多少
int sizeOfStack(Stack* s)
{
    return s->size;
}

//栈是否为空
int isEmpStack(Stack* s)
{
    return s->size<=0;
}

//移动字母
void move(char array[Width][MaxLen],int* len,int start,int end)
{
    char c=array[start][len[start]-1];
    // array[start][len[start]-1]='';
    len[start]--;
    array[end][len[end]]=c;
    len[end]++;
}

//按照字典顺序遍历
int getMoveType(char array[Width][MaxLen],int* len,char endAns,int lastStart,int lastEnd,int* step)
{
    int i=lastStart,j=lastEnd+1;
    for(;i<EndIndex;i++)
    {
        if(len[i]>0)
        {
            j=j>i?j:i+1;
            for(;j<=EndIndex;j++)
            {
                char c=array[i][len[i]-1];
                if(j!=EndIndex||c==endAns)
                {
                    step[0]=c;
                    step[1]=i;
                    step[2]=j;
                    return 1;
                }
            }
            j=0;
        }
    }
    
    return 0;
}

void copyResult(Stack* s,char result[MaxStep][3])
{
    for(int i=0;i<s->size;i++)
    {
        result[i][0]=(char)s->data[i][0];
        result[i][1]=s->data[i][1]+'A';
        result[i][2]=s->data[i][2]+'A';
    }
}

int main(){
    int n;
    scanf("%d",&n);
    char input[MaxLen];
    scanf("%s",&input);
    char array[Width][MaxLen];
    int len[Width];
    int i;
    for(i=0;i<Width;i++)
    {
        len[i]=0;
    }

    len[0]=n;
    for(i=0;i<n;i++)
    {
        array[0][i]='a'+i;
    }
    Stack* s=newStack();
    
    char index=n-1;
    char endAns=input[index];
    //还有多少字母需要操作
    int sumlen=n;

    //存储结果
    char result[MaxStep][3];
    int result_len=0;
    int step[3];
    
    for(i=n;i<=3*n;i++)
    {
        s->size=0;
        do
        {
            int flag=0;
            //搜索可以移动的类型 最重要的剪枝 当前可操作数要大于剩余字母数
            if(sumlen>0&&i-s->size>=sumlen)
            {
                flag=getMoveType(array,len,endAns,0,0,step);
            }
                
            
            //向下搜索
            if(flag){
                //将操作记录压入栈
                pushStack(s,step);
                move(array,len,step[1],step[2]);
                if(step[2]==EndIndex)
                {
                    sumlen--;
                    index--;
                    if(index>=0)
                    {
                        endAns=input[index];
                    }
                    
                }
                
            }
            //回溯
            else{
                //已经找到了结果
                if(sumlen==0)
                {
                    result_len=s->size;
                    copyResult(s,result);   
                    break;
                }

                //回溯
                while (!isEmpStack(s))
                {

                    popStack(s);
                    int start=s->data[s->size][1];
                    int end=s->data[s->size][2];
                    //将字母移动回去
                    move(array,len,end,start);
                    //如果当前是将字母移动到最后一列 重新计算
                    if(end==EndIndex)
                    {
                        sumlen++;
                        index++;
                        endAns=input[index];
            
                    }

                    
                    flag=getMoveType(array,len,endAns,start,end,step);
                    if(flag)
                    {
                        pushStack(s,step);
                        move(array,len,step[1],step[2]);
                        if(step[2]==EndIndex)
                        {
                            sumlen--;
                            index--;
                            if(index>=0)
                            {
                                endAns=input[index];
                            }
                        }
                        break;
                    }
                } 
            }

        }while (!isEmpStack(s));

        if(result_len>0)
        {
            break;
        }
    }
   

    if(result_len==0)
    {
        printf("NO\n");
    }
    else{
        for(i=0;i<result_len;i++)
        {
            printf("%c %c %c\n",result[i][0],result[i][1],result[i][2]);
        }
        
    }
    delete s;
    
    return 0;
}