题目链接：POJ 3087
题意：
有两副牌s1和s2各c张，每张纸牌用一个字符表示纸牌的颜色。还有一副2*c张的纸牌s。
先抽取s2的最底下一张纸牌（第c张），然后抽取s1最底下的一张纸牌（第c张）叠放在其上面，再抽取s2的最底下一张纸牌（此时是初始时的第c-1张）叠放在上面，接着然后抽取s1最底下的一张纸牌（此时也是初始时的第c-1张）叠放在其上面.....最后会形成一副2*c的纸牌，如果这个纸牌的颜色顺序和s不一致，那么抽取下层的c张作为新的s1，上层的c张作为新的s2，重复操作。问能否通过若干次洗牌使得洗出来的纸牌和s颜色顺序一致，若能，输出洗牌次数，否则输出-1.
思路：
判断-1退出的方法有两种。
- 将之前的所有洗牌序列记录下来，一旦新出现的游戏牌序列和之前的有重复那么就可以退出了。记录的方式可以用，map映射，链表，set集合。
- 新拆分出的s1和s2与输入相同，这时也需要退出。这种方法需要一开始就先把s1和s2“复制”保留下来，然后用字符串模拟操作。
下面提供几种解法，一起学习~
/*
*********BFS************
*/
#include <iostream>
#include <map>
#include <string>
#include <queue>
#include <algorithm>
using namespace std;
int n, len, cases;
string s1, s2, s, t;
map<string, int> mp;
//映射mp[t]=num,表示得到洗牌序列t需要洗牌num次
void Shuffle()
{//洗牌t = "";for (int i = 0;i < len;i++){t += s2[i];t += s1[i];}
}
int BFS()
{mp.clear();//每种样例输入需要清空mpqueue<string> q;Shuffle();mp[t] = 1;q.push(t);while (!q.empty()){string front = q.front();q.pop();if (front == s) return mp[front];s1 = front.substr(0, len);//拆分s1和s2s2 = front.substr(len, len);Shuffle();if (mp[t] > 0) return -1;//所洗出来的牌之前已经洗出来过了mp[t] = mp[front] + 1;//得到纸牌序列t的洗牌次数是mp[front] + 1q.push(t);}
}
int main()
{
#ifdef LOCALfreopen("in.txt", "r", stdin);freopen("out.txt", "w", stdout);
#endifcin >> n;for (cases = 1;cases <= n;cases++){cin >> len >> s1 >> s2 >> s;int ans = BFS();cout << cases << " " << ans << endl;}return 0;
}
/*
**********链表***********
*/
#include <iostream>
using namespace std;char s1[100], s2[100], skey[210], stemp[210];
int n, len, cases, cnt;
struct Node {char s[210];struct Node* next;
}*head, *newnode, *tmp, *tail;
void Shuffle()
{for (int i = 0;i < len;i++){stemp[2 * i] = s2[i];stemp[2 * i + 1] = s1[i];}stemp[2 * len] = '\0';
}
int Judge()
{head = (Node*)malloc(sizeof(Node));head->next = NULL;tail = head;cnt = 0;while (1){Shuffle();cnt++;if (strcmp(stemp, skey) == 0) return cnt;tmp = head;while (tmp->next != NULL){if (strcmp(tmp->s, stemp) == 0) return -1;所洗出来的牌之前已经洗出来过了tmp = tmp->next;}newnode = (Node*)malloc(sizeof(Node));//尾插新结点strcpy(newnode->s, stemp);newnode->next = NULL;tail->next = newnode;tail = newnode;for (int i = 0;i < len;i++){//拆分出s1，s2s1[i] = stemp[i];s2[i] = stemp[i + len];}}
}
int main()
{
#ifdef LOCALfreopen("in.txt", "r", stdin);freopen("out.txt", "w", stdout);
#endifcin >> n;for (cases = 1;cases <= n;cases++){cin >> len >> s1 >> s2 >> skey;int ans = Judge();cout << cases << " " << ans << endl;}return 0;
}/*
************集合set*************
*/
#include <iostream>
#include <string>
#include <set>using namespace std;string s1, s2, s, T;
int n, len, cnt, cases;
set<string> myset;void Shuffle()
{T = "";for (int i = 0;i <len;i++){T += s2[i];T += s1[i];}
}
int Judge()
{myset.clear();cnt = 0;while (1){Shuffle();cnt++;if (s == T) return cnt;if (myset.count(T) == 1) return -1;else{s1.assign(T, 0, len);s2.assign(T, len, len);myset.insert(T);}}
}
int main()
{
#ifdef LOCALfreopen("in.txt", "r", stdin);freopen("out.txt", "w",stdout);
#endifscanf("%d", &n);for (cases = 1;cases <= n;cases++){cin >> len >> s1 >> s2 >> s;int ans = Judge();printf("%d %d\n", cases, ans);}return 0;
}/*
***********string类字符串模拟*********
*/
#include <iostream>
#include <string>
#include <set>
using namespace std;int n, cnt, len, cases;
string s1, s2, s, T1, T2, T;void Shuffle()
{s = "";for (int i = 0;i < len;i++){s += s2[i];s += s1[i];}s1 = "";s2 = "";
}int Judge()
{cnt = 0;T1 = s1;T2 = s2;while (1){Shuffle();cnt++;if (s.compare(T)==0) return cnt;for (int i = 0;i < len;i++){s1+= s[i];s2+= s[i + len];}s1[len] = s2[len] = '\0';if (s1.compare(T1) == 0 && s2.compare(T2)==0) return -1;}
}int main()
{
#ifdef LOCALfreopen("in.txt", "r", stdin);freopen("out.txt", "w", stdout);
#endifscanf("%d", &n);for (cases = 1;cases <= n;cases++){cin >> len >> s1 >> s2 >> T;int ans = Judge();printf("%d %d\n", cases, ans);}return 0;
}