#include <iostream>
#include <queue>
#include <cstring>
#include <set>
using namespace std;
struct node
{
	string s;
	int step;
};
set<string>vis;
int n;
int bfs(string a,string b,string res)
{
	queue<node>q;
	node sa;
	string p1=a+b;
	sa.s=p1;
	sa.step=0;
	q.push(sa);
//	vis.insert(p1);
	while(!q.empty())
	{
		
		node temp = q.front();
		if(temp.s==res&&temp.step!=0)
		return temp.step;
		q.pop();
		string x1="";
		for(int i =0;i < n;i++)
		{
			x1+=temp.s[i];
			x1+=temp.s[i+n];

		}
		if(vis.find(x1)==vis.end())
		{
			node tempres;
			tempres.s=x1;
			tempres.step=temp.step+1;
			vis.insert(x1);
			q.push(tempres);
		}
		else
			return -1;
	}

		
}
int main()
{
	int T;
	cin >> T;
	for(int i =1;i <=T;i++)
	{
		cin >> n;
		string s1,s2,sr;
		cin >> s1>>s2>>sr;
		int ans;
		string sr1="";
		string sr2="";
		string srr="";
		for(int j =2*n-1;j >=0;j--)
		{
			srr+=sr[j];
			if(j<=n-1)
			{
				sr1+=s1[j];
				sr2+=s2[j];	
			}		
		}
		
//		cout << sr1<<" "<<sr2<<" "<<srr<< endl;	
		ans=bfs(sr1,sr2,srr);
		cout <<i <<" " <<ans << endl;
		vis.clear();
		
	}
}

• Re:求助，一直WA，我用的bfs+set判重 (15) God_Neptune_Poseidon 2015-08-12 11:31:57