题目链接：http://poj.org/problem?id=3087
题目大意：给定三堆牌，前两堆数目均为c，第三堆数目为2*c。
给定洗牌规则，问经过多少次洗牌才能到达第三堆牌的状态。如果不可能到第三堆牌的状态，输出-1。
解题思路：bfs模拟。
用字符串描述牌的状态。用set来标记该字符串是否出现过，如果第二次出现，说明已经陷入了循环，不可能得到结果。
开始先把s1和s2洗完，步数加一，放进set。然后判断该状态是否满足，如果不满足，则将该牌按规则分开，再次洗牌。
直到洗完的牌的状态满足了所要求的状态。输出结果。如果没有结果，则循环过程中该状态一定会重复出现。则将step置为-1.跳出循环。
代码入下：
1 #include<cstdio> 2 #include<string> 3 #include<set> 4 #include<iostream> 5 using namespace std; 6 7 int c,step; 8 char s1[105],s2[105],s[210];//记录三个串 9 set<string> vis;//用来判重，防止陷入死循环 10 11 string shuffle(string s1,string s2)//洗牌一次，得到新的牌 12 { 13 string temp=""; 14 for(int i=0;i<c;i++) 15 { 16 temp+=s2[i]; 17 temp+=s1[i]; 18 } 19 return temp; 20 } 21 22 void bfs() 23 { 24 vis.clear(); 25 26 string temp=shuffle(s1,s2);//洗一次牌 27 vis.insert(temp);//标记这种结果出现过了 28 step=1;//步数加一 29 30 while(temp!=s)//一直洗牌 31 { 32 temp=shuffle(temp.substr(0,c),temp.substr(c,c));//将temp牌分开，再次洗牌 33 step++;//步数加一 34 if(vis.find(temp)!=vis.end())//如果得到的这种结果以前已经出现过了，说明无论如何得不到题目中所要求的结果 35 { 36 step=-1; 37 break; 38 } 39 vis.insert(temp);//将该结果标记 40 } 41 printf("%d\n",step);//输出总的步数 42 } 43 44 int main() 45 { 46 int cases; 47 int num=1; 48 scanf("%d",&cases); 49 while(cases--) 50 { 51 cin>>c>>s1>>s2>>s; 52 printf("%d ",num++); 53 bfs(); 54 } 55 return 0; 56 }
原文：http://www.cnblogs.com/Page3/p/4646183.html
