洗牌
↑ 题目链接
题目
给定两叠纸牌 \(S1\) 和 \(S2\)，每叠恰好有 \(C\) 张牌。
每张牌的尺寸大小都完全相同，但是颜色可能不同。
下面介绍洗牌规则。
不妨设 \(S1\) 中纸牌从上到下编号依次为 \(a_1,a_2,…,a_C\) ，\(S_2\) 中纸牌从上到下编号依次为 \(b_1,b_2,…,b_C\) 。
洗牌就是将这两叠牌交错堆叠在一起，形成一个拥有 \(2C\) 张牌的新牌堆 \(S_{12}\) 。
新牌堆中的牌由上至下依次为 \(a_1,b_1,a_2,b_2,…,a_C,b_C\) 。
然后，将牌堆从中间一分为二，下半部分是新的 \(S_1\)，上半部分是新的 \(S2\) 。
这样就可以继续进行洗牌操作获得新的 \(S_{12}\) 了。
给定 \(S_1\) 和 \(S_2\) ，请问至少需要进行多少轮洗牌操作方可获得指定牌堆 \(S_{12}\)。
输入格式
第一行包含一个整数 \(T\) ，表示共有 \(T\) 组测试数据。
每组数据第一行包含一个整数 \(C\)。
第二行包含一个长度为 \(C\) 的由大写字母构成的字符串，其中第 \(i\) 个字母表示初始 \(S_1\) 中由底向上第 \(i\) 张牌的颜色。
第三行包含一个长度为 \(C\) 的由大写字母构成的字符串，其中第 \(i\) 个字母表示初始 \(S2\) 中由底向上第 \(i\) 张牌的颜色。
第四行包含一个长度为 \(2C\) 的由大写字母构成的字符串，其中第 \(i\) 个字母表示目标 \(S_{12}\) 中由底向上第 \(i\) 张牌的颜色。
输出格式
共 \(T\) 行，每行输出一组数据的结果，首先输出组别编号 \(i\)（从1开始），
然后输出所需要的最少洗牌次数。如果无法通过洗牌获得目标牌堆，则输出 −1。
数据范围
\(1≤T≤1000,1≤C≤100\)
卡牌最多有 \(8\) 种颜色，用大写字母 \(A∼H\) 表示，所以输入字符串中不会出现其他大写字母。
输入样例：
2
4
AHAH
HAHA
HHAAAAHH
3
CDE
CDE
EEDDCC
输出样例：
1 2
2 -1
思路
按照题意，通过 \(BFS\) 搜索情况，,最多枚举 \(2C\) 次,就可以知道能否得到该字符串
代码
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+10;
int n;
int bfs(string a,string b,string c)
{
queue<string>q;
map<string,int>d;
string tem;
for(int i=0;i<n;i++)//第一次洗牌
{
tem+=b[i];
tem+=a[i];
}
q.push(tem);
d[tem]=1;
while(q.size())
{
auto t=q.front();
q.pop();
if(t==c)return d[c];//搜到合法方案
string tem2;
for(int i=0;i<n;i++)//重新洗牌
{
tem2+=t[i+n];
tem2+=t[i];
}
if(d.count(tem2))return -1;//产生循环，无解
d[tem2]=d[t]+1;
q.push(tem2);
}
return -1;
}
int main()
{
int T;
cin>>T;
for(int i=1;i<=T;i++)
{
string a,b,c;
cin>>n>>a>>b>>c;
printf("%d %d\n",i,bfs(a,b,c));
}
return 0;
}