$$\color{Purple}{kuangbin题解目录}$$
描述
给定两叠纸牌 $S_1$ 和 $S_2$,每叠恰好有 $C$ 张牌。
每张牌的尺寸大小都完全相同,但是颜色可能不同。
下面介绍洗牌规则。
不妨设 $S_1$ 中纸牌从上到下编号依次为 $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$,上半部分是新的 $S_2$。
这样就可以继续进行洗牌操作获得新的 $S_{12}$ 了。
给定 $S_1$ 和 $S_2$,请问至少需要进行多少轮洗牌操作方可获得指定牌堆 $S_{12}$。
输入格式
第一行包含一个整数 $T$,表示共有 $T$ 组测试数据。
每组数据第一行包含一个整数 $C$。
第二行包含一个长度为 $C$ 的由大写字母构成的字符串,其中第 $i$ 个字母表示初始 $S_1$ 中由底向上第 $i$ 张牌的颜色。
第三行包含一个长度为 $C$ 的由大写字母构成的字符串,其中第 $i$ 个字母表示初始 $S_2$ 中由底向上第 $i$ 张牌的颜色。
第四行包含一个长度为 $2C$ 的由大写字母构成的字符串,其中第 $i$ 个字母表示目标 $S_{12}$ 中由底向上第 $i$ 张牌的颜色。
输出格式
共 $T$ 行,每行输出一组数据的结果,首先输出组别编号 $i$(从 $1$ 开始),然后输出所需要的最少洗牌次数。如果无法通过洗牌获得目标牌堆,则输出 $\-1$。
数据范围
$1 \\le T \\le 1000$,
$1 \\le C \\le 100$。
卡牌最多有 $8$ 种颜色,用大写字母 $A \\sim H$ 表示,所以输入字符串中不会出现其他大写字母。
输入样例:
2
4
AHAH
HAHA
HHAAAAHH
3
CDE
CDE
EEDDCC
输出样例:
1 2
2 -1
思路
此题为模拟+bfs(可不用bfs),最多枚举$2C$次模拟操作,就可以知道能否得到该字符串.
代码
#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
#include <cstdio>
#include <map>
using namespace std;
int t,n,cas=1;
string s1,s2,res;
void bfs()
{
string temp;
for(int i=0;i<n;i++)
temp+=s2[i],temp+=s1[i];
map<string,int> mp;
queue<string> q;
q.push(temp);
mp[temp]=1;
while(q.size()>0)
{
string t=q.front();
q.pop();
if(t==res)
{
printf("%d %d\n",cas++,mp[t]);
return ;
}
string now;
for(int i=0;i<n;i++)
now+=t[i+n],now+=t[i];
if(mp[now]==0)
{
mp[now]=mp[t]+1;
q.push(now);
}
}
printf("%d -1\n",cas++);
}
int main()
{
scanf("%d",&t);
while(t--)
{
scanf("%d",&n);
cin >> s1 >> s2 >> res;
bfs();
}
return 0;
}