http://poj.org/problem?id=3087
用bfs写的，但是其实就是个模拟啊喂！
只有一种操作，何谈最短？ 一直往下写就行了．
有一点疑惑，就是map的初始值
比如我定义的 map<string,int>d;它的初始的value是什么？随机值？０？还是什么，百度了下，没找到，求指教．
1
2 #include<iostream>
3 #include<iomanip>
4 #include<cstdio>
5 #include<algorithm>
6 #include<cmath>
7 #include<cstring>
8 #include<string>
9 #include<map>
10 #include<set>
11 #include<queue>
12 #include<vector>
13 #include<stack>
14 #define y0 abc111qqz
15 #define y1 hust111qqz
16 #define yn hez111qqz
17 #define j1 cute111qqz
18 #define tm crazy111qqz
19 #define lr dying111qqz
20 using namespace std;
21 #define REP(i, n) for (int i=0;i<int(n);++i)
22 typedef long long LL;
23 typedef unsigned long long ULL;
24 map<string,int>d;
25 string st1,st2,tar;
26 int n;
27 bool flag;
28 string add(string a,string b)
29 {
30 string res="";
31 int len = a.length();
32 for ( int i = 0 ; i < len ; i++ )
33 {
34 res+=b[i];
35 res+=a[i];
36 }
37 return res;
38 }
39 void bfs()
40 {
41 queue<string>q;
42 string str=add(st1,st2);
43 q.push(str);
44 d[str]=1;
45 while (!q.empty())
46 {
47 string pst = q.front();
48 q.pop();
49 if (pst==tar)
50 {
51 flag = true;
52 return;
53 }
54 string s1=pst.substr(0,n);
55 string s2=pst.substr(n,n);
56 string tmps = add(s1,s2);
57 if (d[tmps]>0)
58 {
59 flag = false;
60 return;
61 }
62 d[tmps]=d[pst]+1;
63 q.push(tmps);
64 }
65 }
66 int main()
67 {
68 int T;
69 int cas = 0;
70 cin>>T;
71
72 while (T--)
73 {
74 d.clear();
75 cas++;
76 cin>>n;
77 cin>>st1>>st2>>tar;
78 bfs();
79 if (flag)
80 {
81 cout<<cas<<" "<<d[tar]<<endl;
82 }
83 else
84 {
85 cout<<cas<<" "<<-1<<endl;
86 }
87 }
88
89 return 0;
90 }