想多了！以为一直dfs所有的情况会超时，所以直接忽略了，就自己想了一个优化的算法，最后测试结果对了，但是wa了，自己写算法很容易考虑不周的，还是在最后没有办法的时候在考虑自己的算法吧！！！简单的dfs就可以了！
|
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
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70 |
#include<stdio.h>#include<string.h>#define Max 100char goal_str[Max];char source_str[Max];char stack[Max];int path[Max];int lenth,top,pointer;void
print_path(void){ int
i; for(i=0;i<2*lenth;i++) { if(path[i]==1) printf("i "); else printf("o "); } printf("\n");}void
dfs(int
npush,int
npop){ char
tmp; if(npush==lenth&&npop==lenth) { print_path(); return
; } if(npush<lenth) { path[pointer++]=1; stack[top++]=source_str[npush]; dfs(npush+1,npop); top--; pointer--; } if(top>0&&stack[top-1]==goal_str[npop]) { tmp=stack[top-1]; path[pointer++]=-1; top--; dfs(npush,npop+1); pointer--; top++; stack[top-1]=tmp; }}int
main(){ int
n1; while(scanf("%s%s",source_str,goal_str)!=EOF) { pointer=0; top=0; printf("[\n"); lenth=strlen(source_str); n1=strlen(goal_str); if(n1==lenth) dfs(0,0); printf("]\n"); } return
0;} |
原文：http://www.cnblogs.com/woshijishu3/p/3636941.html