Shuffle'm Up (map ➕ BFS)
题目链接：http://poj.org/problem?id=3087
题目大意：给你一个字符串s1、一个字符串 s2 和一个期望得到的字符串 ，每次先放一个s2 再放一个 s1 ，得到一个新的字符串，然后取这个新字符串的前一半为s1 后一半为 s2
问最少经过几次变换可以得到期望的字符串
思路：
利用 map函数去标记每个字符串，如果重复出现了则说明它进入了循环，也就是说不可能得到我们期望的字符串了。
BFS 的过程还是非常普遍的
1 #include <iostream> 2 #include <string> 3 #include <cstring> 4 #include <queue> 5 #include <string.h> 6 #include <stdio.h> 7 #include <map> 8 9 using namespace std; 10 11 const int maxn = 1005; 12 13 map<string,int> d; 14 typedef struct Node{ 15 string val; 16 int cnt; 17 }Node; 18 19 int n; 20 int T; 21 string s1,s2,es,str; 22 23 24 int bfs() 25 { 26 queue<Node> q; 27 Node node; 28 for (int i=0;i<s1.length();i++) 29 { 30 str += s2[i]; 31 str += s1[i]; 32 } 33 node.val = str; 34 node.cnt = 1; 35 d[str] = 1; 36 q.push(node); 37 while (!q.empty()) 38 { 39 Node cur = q.front(); 40 q.pop(); 41 if (cur.val == es) 42 { 43 return cur.cnt; 44 } 45 s1 = cur.val.substr(0,n); 46 s2 = cur.val.substr(n,n); 47 str = ""; 48 for (int i=0;i<s1.length();i++) 49 { 50 str += s2[i]; 51 str += s1[i]; 52 } 53 cur.val = str; 54 if (d[cur.val]) 55 return -1; 56 d[str] = 1; 57 cur.cnt++; 58 q.push(cur); 59 } 60 } 61 62 63 int main() 64 { 65 cin >> T; 66 int t = 1; 67 while (T--) 68 { 69 str = ""; 70 cin >> n; 71 cin >> s1; 72 cin >> s2; 73 cin >> es; 74 int ant = bfs(); 75 printf("%d ",t++); 76 printf("%d\n",ant); 77 } 78 return 0; 79 }