BruteForce，纯模拟吧，无解时会回到初始态。
不过这题好像有数学方法的，
而且任何情况都会回到初始态，
这个应该有证明。
还记得有一道题是求回到初始态的步数。。
总之是用BF秒过了。。
更多深入以后研究。
PKU3087
1/**//*
2
Task: pku3087
3Author: DMKaplony
4Date: 04/03/2010 11:16:17 China Standard Time
5State:
6 6511528 DMKaplony 3087 Accepted 180K 0MS C++ 1729B 2010-03-04 11:32:06
7Memo: BruteForce--Forxcc0322
8
*/
9
10#include <iostream>
11
12#define MAXL 3000
13
14using namespace std;
15
16char a[MAXL], b[MAXL], aa[MAXL], bb[MAXL], g[MAXL];
17int n;
18
19bool NoAnswer()
{
20 int i;
21
for (i=1; i<n+1; i++){
22 if (a[i] != aa[i] || b[i] != bb[i])
23 return false;
24
}
25 return true;
26 }
27int Check(){
28 if (NoAnswer()){
29 return -1;
30 }
31 for (int i=1; i<n+1; i++){
32 if (a[i] != g[i] || b[i] != g[n + i])
33 return 0;
34 }
35 return 1;
36 }
37
38void Alter(){
39 char tmp[MAXL];
40 int i;
41 for (i=1; i<n+1; i++){
42 tmp[(i << 1) - 1] = b[i];
43 tmp[i << 1] = a[i];
44 }
45 for (i=1; i<n+1; i++){
46 a[i] = tmp[i];
47 b[i] = tmp[n + i];
48 }
49 }
50int main(){
51 int cases;
52 scanf("%d", &cases);
53 for (int o=1; o<cases+1; o++){
54 scanf("%d", &n);
55 int i;
56 for (i=1; i<n+1; i++){
57 scanf(" %c", &a[i]);
58 }
59 for (i=1; i<n+1; i++){
60 scanf(" %c", &b[i]);
61 }
62 //
63 for (i=1; i<(n << 1)+1; i++){
64 scanf(" %c", &g[i]);
65 }
66 //
67 memcpy(aa, a, sizeof(a));
68 memcpy(bb, b, sizeof(b));
69 int ret;
70 int counter = 1;
71 Alter();
72 while (1){
73 ret = Check();
74 if (ret)
75 break;
76 Alter();
77 counter++;
78 }
79 if (ret == -1)
80 printf("%d %d\n", o, ret);
81 else
82 printf("%d %d\n", o, counter);
83 }
84 return 0;
85 }
86