题目解析

题意分析

这道题目模拟了扑克筹码的洗叠过程，要求计算从初始堆 $S1$ 和 $S2$ 通过特定洗牌规则重组后，达到目标 $S12$ 所需的最少洗牌次数。具体规则如下：

1. 初始状态：

   • 两个筹码堆 $S1$ 和 $S2$，每堆包含 $C$ 个筹码（$1 \leq C \leq 100$）
   • 每个筹码用大写字母 $A$-$H$ 表示颜色

2. 洗牌规则：

   • 新建空堆 $S12$（最终包含 $2 \times C$ 个筹码）
   • 交替从 $S2$ 和 $S1$ 的最底层开始取筹码：
     • 第 $i$ 次操作（$1 \leq i \leq C$）：
       • $S12[2i-1] = S2[i]$
       • $S12[2i] = S1[i]$

3. 重组规则：

   • 每次洗牌后，将 $S12$ 拆分为：
     • 新 $S1$：取 $S12$ 前 $C$ 个筹码（底层）
     • 新 $S2$：取 $S12$ 后 $C$ 个筹码（顶层）

4. 目标：

   • 判断经过多少次洗牌后，$S12$ 能等于目标序列
   • 若无法达成目标，则输出 $-1$

解题思路

1. 模拟洗牌过程：

   • 根据洗牌规则，每次洗牌生成新的 $S12$ 序列
   • 将 $S12$ 拆分为新的 $S1$ 和 $S2$ 用于下一次洗牌

2. 检测循环：

   • 使用集合记录每次洗牌后的 $S1$ 和 $S2$ 状态
   • 如果状态重复出现，说明进入无限循环，无法达成目标

3. 终止条件：

   • 当前 $S12$ 等于目标序列时，返回洗牌次数
   • 若洗牌次数超过 $2 \times C$ 次仍未达成目标，则认为无法达成

#include<string.h>
#include<string>
#include<queue>
#include<cstdio>
#include<algorithm>
#include<iostream>
using namespace std;
 
string a,b,target;
int num;
 
int  dfs(string s1,string s2,int step){
    if(s1+s2==target)
          return step;
    string temp="";
    for(int i=0;i<num;i++)  temp=temp+s2[i]+s1[i];
    s1=temp.substr(0,num);
    s2=temp.substr(num,num);
    if(s1.compare(a)==0&&s2.compare(b)==0)
          return -1;
    else
          return dfs(s1,s2,step+1);
}
 
int main()
{
    int Case;
    cin>>Case;
    for(int T=1;T<=Case;T++){
        cin>>num>>a>>b>>target;
        cout<<T<<' '<<dfs(a,b,0)<<endl;
    }
    return 0;
}