已知两堆牌s1和s2的初始状态， 其牌数均为c，按给定规则能将他们相互交叉组合成一堆牌s12，再将s12的最底下的c块牌归为s1，最顶的c块牌归为s2，依此循环下去。
现在输入s1和s2的初始状态 以及 预想的最终状态s12
问s1 s2经过多少次洗牌之后，最终能达到状态s12，若永远不可能相同，则输出”-1”。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
using namespace std;
int ans,n;
map<string,int>m;
char s1[200],s2[200],s3[200];
void dfs(char s[],int step){
if((ans=-1&&step>=ans)||m[s])return;
if(m[s])return;
if(!strcmp(s,s3)){ans=step;return ;}
m[s]=true;
char ss[200]="";
int op=0;
for(int i=0;i<n;++i)
{
ss[op++]=s[i+n];
ss[op++]=s[i];
}
dfs(ss,step+1);
}
int main(){
int t;
char ss[200];
scanf("%d",&t);
for(int ca=1;ca<=t;++ca){
ans=-1;
m.clear();// map<>
scanf("%d",&n);
scanf("%s",s1);
scanf("%s",s2);
scanf("%s",ss);
char s[200];
int op=0;
for(int i=0;i<n;++i){
s[op++]=s1[i];
s[op++]=s2[i];
}
dfs(s,1);
printf("%d %d\n",ca,ans);
}
}
模拟：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
using namespace std;
int main()
{
int t;
scanf("%d",&t);
for(int ca=1;ca<=t;++ca){
int n;
char s1[1005],s2[1005],en[10000];
map<string,bool >m;
scanf("%d",&n);
scanf("%s",s1);
scanf("%s",s2);
scanf("%s",en);
int step=0;
int times=1000,ti=0;
while(true){
ti++;
char s[1000];
int pc=0;
for(int i=0;i<n;++i){
s[pc++]=s2[i];
s[pc++]=s1[i];
}
s[pc]='\0';
step++;
if(!strcmp(s,en)){
printf("%d %d\n",ca,step);
break;
}
if(m[s]){
printf("%d %d\n",ca,-1);
break;
}
m[s]=true;
strncpy(s1,s,n);
s1[n]='\0';
strncpy(s2,s+n,n);
s2[n]='\0';
if(ti==times){
printf("%d %d\n",ca,-1);
break;
}
}
}
return 0;
}