poj 3087 Shuffle'm Up (bfs)

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