hdu1515 hdu1401 搜索

hdu1515

Anagrams by Stack

深搜能过，想好搜索技巧，很容易过。

题意：给你两个字符串，问：第一个字符串按入栈出栈规则，能否达到第二个字符串，输出所有的方法，i表示入栈，o表示出栈。

用dfs模拟第一个字符串入栈出栈过程:

1. 当前字符入栈，就向下一层递归，即搜向下一个字符

2. 栈顶元素出栈，对新的栈顶元素判断

这题要求按字典序输出，这种先判断入，再判断出的方法正好符合。

1 #include < stdio.h >
2 #include < string .h >
3   int len1, len2;
4 char stack[ 200 ];
5 char s1[ 100 ], s2[ 100 ];
6 char ans[ 200 ];
7 void dfs( int cur, int top, int idx, int step){
8 int i, t, tmp;
9 if (idx == len2){
10 for (i = 0 ; i < step; i ++ ){
11 printf( " %c " , ans[i]);
12 }
13 puts( "" );
14 return ;
15 }
16 if (cur < len1){
17 t = top + 1 ;
18 tmp = stack[t]; // 将栈中元素暂存
19 stack[t] = s1[cur];
20 ans[step] = ' i ' ;
21 dfs(cur + 1 , t, idx, step + 1 );
22 stack[t] = tmp; // 把栈中元素恢复
23 }
24 if (top == - 1 ) return ;
25 if (stack[top] == s2[idx]){
26 ans[step] = ' o ' ;
27 t = top - 1 ;
28 dfs(cur, t, idx + 1 , step + 1 );
29 }
30 }
31 int main()
32 {
33 while (scanf( " %s%s " , s1, s2) != EOF){
34 len1 = strlen(s1);
35 len2 = strlen(s2);
36 if (len1 < len2){
37 printf( " [\n]\n " );
38 continue ;
39 }
40 puts( " [ " );
41 dfs( 0 , - 1 , 0 , 0 );
42 puts( " ] " );
43 }
44 return 0 ;
45 }
46

hdu1401

Solitaire

题意：在8 * 8 的跳棋棋盘上，给你两个状态，每个状态4个点，判断一个状态8步内能否到达另一个状态。

解法：广搜。每个状态4个棋子，每个棋子一步有4种走法，就是说，一个状态有16个后继状态，为了节省空间，用双向BFS，两个状态同时入队，交替着搜，各搜4步，判断有没有可能到达，我这里为了省便，初状态先搜了4步，将所有状态用二进制压缩成一个整数，用set容器存下来，再由终点状态搜4步，判断能不能到达由起点状态到达的任一状态，从而判断能否两个状态8步以内转换。

1 #include < stdio.h >
2 #include < stdlib.h >
3 #include < set >
4 using namespace std;
5 int ok;
6 unsigned __int64 ans;
7 int dir[ 4 ][ 2 ] = { 0 , 1 , 1 , 0 , - 1 , 0 , 0 , - 1 };
8 typedef struct node{
9 int x[ 5 ];
10 int y[ 5 ];
11 int n;
12 }NODE;
13
14 NODE sta, end, que[ 106540 ];
15 set < unsigned __int64 > se;
16 int Judge( int x[], int y[], int nxtx, int nxty, int i){
17 int k;
18 for (k = 0 ; k < 4 ; k ++ ){
19 if (k == i){
20 continue ;
21 }
22 if (x[k] == nxtx && y[k] == nxty){
23 return 0 ;
24 }
25 }
26 return 1 ;
27 }
28
29 void putin(NODE a){
30 int i;
31 ans = 0 ;
32 for (i = 0 ; i < 4 ; i ++ ){
33 ans += (unsigned __int64) 1 << ((a.x[i] - 1 ) * 8 + a.y[i] - 1 );
34 }
35 se.insert(ans);
36 }
37 void bfs1(){
38 NODE cur, nxt;
39 que[ 0 ] = sta;
40
41 int head, tail, i, j, t1, t2, k;
42 putin(sta);
43 head = tail = 0 ;
44 while (head <= tail){
45 cur = que[head ++ ];
46 /* for (k = 0; k < 4; k++){
47 printf("%d %d ", cur.x[k], cur.y[k]);
48 } */
49 for (i = 0 ; i < 4 ; i ++ ){
50
51 for (j = 0 ; j < 4 ; j ++ ){
52 nxt = cur;
53 nxt.n = cur.n + 1 ;
54 if (nxt.n > 4 ) return ;
55 nxt.x[j] = dir[i][ 0 ] + cur.x[j];
56 nxt.y[j] = dir[i][ 1 ] + cur.y[j];
57 if (nxt.x[j] >= 1 && nxt.x[j] <= 8 && nxt.y[j] >= 1 && nxt.y[j] <= 8 ){
58 if (Judge(cur.x, cur.y, nxt.x[j], nxt.y[j], j)){
59 t1 = se.size();
60 putin(nxt);
61 t2 = se.size();
62 if (t1 != t2){
63 que[ ++ tail] = nxt;
64 }
65 } else {
66 nxt.x[j] = dir[i][ 0 ] + nxt.x[j];
67 nxt.y[j] = dir[i][ 1 ] + nxt.y[j];
68 if (nxt.x[j] >= 1 && nxt.x[j] <= 8 && nxt.y[j] >= 1 && nxt.y[j] <= 8 ){
69 if (Judge(cur.x, cur.y, nxt.x[j], nxt.y[j], j)){
70 t1 = se.size();
71 putin(nxt);
72 t2 = se.size();
73 if (t1 != t2){
74 que[ ++ tail] = nxt;
75 }
76 }
77 }
78 }
79 }
80 }
81 }
82 }
83 }
84
85 void bfs2(){
86 NODE cur, nxt;
87 que[ 0 ] = end;
88
89 int head, tail, i, j, t1, t2;
90 t1 = se.size();
91 putin(end);
92 t2 = se.size();
93 if (t1 == t2){
94 ok = 1 ;
95 return ;
96 }
97 se.erase(ans);
98 head = tail = 0 ;
99 while (head <= tail){
100 cur = que[head ++ ];
101 for (i = 0 ; i < 4 ; i ++ ){

104 for (j = 0 ; j < 4 ; j ++ ){
105 nxt = cur;
106 nxt.n = cur.n + 1 ; if (nxt.n > 4 ) return ;
107 nxt.x[j] = dir[i][ 0 ] + cur.x[j];
108 nxt.y[j] = dir[i][ 1 ] + cur.y[j];
109 if (nxt.x[j] >= 1 && nxt.x[j] <= 8 && nxt.y[j] >= 1 && nxt.y[j] <= 8 ){
110 if (Judge(cur.x, cur.y, nxt.x[j], nxt.y[j], j)){
111 que[ ++ tail] = nxt;
112 t1 = se.size();
113 putin(nxt);
114 t2 = se.size();
115 if (t1 == t2){
116 ok = 1 ;
117 return ;
118 }
119 se.erase(ans);
120 } else {
121 nxt.x[j] = dir[i][ 0 ] + nxt.x[j];
122 nxt.y[j] = dir[i][ 1 ] + nxt.y[j];
123 if (nxt.x[j] >= 1 && nxt.x[j] <= 8 && nxt.y[j] >= 1 && nxt.y[j] <= 8 ){
124 if (Judge(cur.x, cur.y, nxt.x[j], nxt.y[j], j)){
125 que[ ++ tail] = nxt;
126 t1 = se.size();
127 putin(nxt);
128 t2 = se.size();
129 if (t1 == t2){
130 ok = 1 ;
131 return ;
132 }
133 se.erase(ans);
134 }
135 }
136 }
137 }
138 }
139 }
140 }
141 }
142 int main()
143 {
144 int i;
145 while (scanf( " %d%d " , & sta.x[ 0 ], & sta.y[ 0 ]) != EOF){
146 for (i = 1 ; i <= 3 ; i ++ ){
147 scanf( " %d%d " , & sta.x[i], & sta.y[i]);
148 }
149 sta.n = 0 ;
150 for (i = 0 ; i <= 3 ; i ++ ){
151 scanf( " %d%d " , & end.x[i], & end.y[i]);
152 }
153 end.n = 0 ;
154 ok = 0 ;
155 bfs1();
156 bfs2();
157 if (ok) puts( " YES " );
158 else puts( " NO " );
159 se.clear();
160 }
161 return 0 ;
162 }
163

代码重复性很高，可以稍作处理，减少代码量。这里用set判重，如果set的大小没变，说明加入的值已存在。

加几组数据：

1 4 3 7 4 5 6 2 1 4 3 7 4 5 6 2

2 1 8 8 7 8 1 1 1 5 8 7 7 7 2 4

6 5 5 7 5 1 7 1 7 7 6 5 5 7 6 3

4 6 5 6 5 5 5 2 2 2 7 6 5 3 5 2

4 4 5 5 3 4 7 2 2 7 7 2 6 5 4 8

4 2 3 4 5 5 6 6 2 7 4 4 3 5 4 5

3 3 5 3 6 2 6 6 6 3 8 3 6 6 6 8

3 2 5 3 6 2 6 6 6 3 8 3 6 6 6 8

3 4 4 5 5 5 7 5 3 3 4 3 5 3 6 3

解为：

YES

YES

YES

YES

YES

YES

YES

NO

YES