POJ 3087
题目意思读懂:给出字符串s1,s2,ans,创建一个空字符串s12,将s2第一个放在s12第一个,s1第一个放在s12第二个,然后依次类推,s12前一半是新的s1,后一半是新的s2,输出模拟后s12 == ans的步数(BFS),否则输出-1,map<string,bool>标记就行了 #include <iostream> #include <string> #include <map> #include <queue> using namespace std; map<string,bool> vis; int len; string a,b,c; struct node { string sa; string sb; int step; node(); node(string s1,string s2,int step) { this->sa = s1; this->sb = s2; this->step = step; } }; int bfs() { vis.clear(); queue< node > que; que.push( node(a,b,0) ); while ( !que.empty() ) { node cur = que.front(); que.pop(); string nes; int index1 = 0,index2 = 0; for (int i=0; i<2*len; i++) { if (i % 2 == 0) { nes += cur.sb[index2++]; } else { nes += cur.sa[index1++]; } } if (nes == c) { // 等于c 肯定没出现 return cur.step+1; } else if (vis[nes] && nes != c) { // 出现了一次,并且不是结果 return -1; } else { vis[nes] = 1; string s1 = nes.substr(0,len); string s2 = nes.substr(len,len); node nex(s1,s2,cur.step+1); que.push(nex); } } return -1; } int main() { // freopen("a.txt","r",stdin); int times; cin >> times; int cnt = 0; while (++cnt <= times) { cin >> len; cin >> a >> b >> c; vis[c] = 1; cout << cnt <<" "<< bfs() << endl; } return 0; }