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;
  }