在读《挑战程序设计竞赛》时，想到了以前玩的一个小游戏—青蛙交换位置游戏。
游戏说明:
(1) 用鼠标点青蛙头部向前跳，两边不同顏色的青蛙互換位置是最終目標.
(2) 可以前進一步.
(3) 最多只能跳過一個青蛙.
(4) 一次一步，不限顏色
(5) 只能前進.不能後退.
(6) 按红色箭头，游戏复原。
(7) 此题肯定有解，不要怀疑。
本文用DFS搜索算法求解了这个游戏。
类似的问题都可以按部就班地求解。
第一步，定义状态。
状态定义为char[7]数组，表示图中的7个位置，向右跳的青蛙记为’R’， 向左跳的青蛙记为’L’，空白位置记为空格’ ’。所以初始状态为[RRR LLL]。
代码中，状态用结构体state_t表示。
bool check_finish(state_t state)函数用于检查给定的状态是否是终止状态。
第二步，定义获取下一个状态。
按照题目描述的跳跃规则，给定一个状态时，我们能够求出该状态能够产生的新的状态。例如，从[RRR LLL]能够产生[RR RLLL]，[RRRL LL]等。
代码中，list get_children(state_t state)函数用于产生下一个状态列表。
第三步，执行DFS进行搜索。
搜索框架也是非常确定的结构。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| bool dfs(state_t state){
if(check_finish(state)){
cout<<"Finish!"<<endl;
print_stack();
return true;
}
list<state_t> children = get_children(state);
list<state_t>::iterator iter = children.begin();
for( ; iter != children.end(); iter++){
state_stack[stack_top++] = (*iter);
if(dfs(*iter))
return true;
stack_top--;
}
return false;
}
|
好了，就这三步，是不是很简单？
完整的代码大约只有100多行，本文罗列如下。
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
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
| #include <iostream>
#include <list>
using namespace std;
typedef struct state {
char state_array[7];
}state_t;
void move(state_t& state, int from, int to){
char tmp = state.state_array[from];
state.state_array[from] = state.state_array[to];
state.state_array[to] = tmp;
}
inline bool check_finish(state_t state){
return state.state_array[0] == 'R' &&
state.state_array[1] == 'R' &&
state.state_array[2] == 'R' &&
state.state_array[3] == ' ';
}
#define SIZE 25
state_t state_stack[SIZE];
int stack_top=0;
void print_state(state_t state){
int i;
for(i=0; i<7; i++){
cout<<state.state_array[i];
}
cout<<endl;
}
void print_stack(){
int i;
for(i=0; i<stack_top; i++){
print_state(state_stack[i]);
}
}
list<state_t> get_children(state_t state){
list<state_t> children;
int blank;
for(blank = 0; blank < 7; blank++){
if(state.state_array[blank] == ' ')
break;
}
if(blank+1<=6 && state.state_array[blank+1]=='R'){
state_t child = state;
move(child, blank+1, blank);
children.push_back(child);
}
if(blank+2<=6 && state.state_array[blank+2]=='R'){
state_t child = state;
move(child, blank+2, blank);
children.push_back(child);
}
if(blank-1>=0 && state.state_array[blank-1]=='L'){
state_t child = state;
move(child, blank-1, blank);
children.push_back(child);
}
if(blank-2>=0 && state.state_array[blank-2]=='L'){
state_t child = state;
move(child, blank-2, blank);
children.push_back(child);
}
return children;
}
bool dfs(state_t state){
if(check_finish(state)){
cout<<"Finish!"<<endl;
print_stack();
return true;
}
list<state_t> children = get_children(state);
if(children.size()==0)
return false;
list<state_t>::iterator iter = children.begin();
for( ; iter != children.end(); iter++){
state_stack[stack_top++] = (*iter);
if(dfs(*iter))
return true;
stack_top--;
}
return false;
}
int main(){
state_t root;
root.state_array[0] = 'L';
root.state_array[1] = 'L';
root.state_array[2] = 'L';
root.state_array[3] = ' ';
root.state_array[4] = 'R';
root.state_array[5] = 'R';
root.state_array[6] = 'R';
dfs(root);
return 0;
}
|
执行结果如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| Finish!
LLLR RR
LL RLRR
L LRLRR
LRL LRR
LRLRL R
LRLRLR
LRLR RL
LR RLRL
RLRLRL
R LRLRL
RRL LRL
RRLRL L
RRLR LL
RR RLLL
RRR LLL
|
