深度优先搜索求解青蛙交换位置小游戏
用DFS搜索算法求解青蛙交换位置游戏。详细描述了算法的步骤和代码结构,包括描述状态的表示,获取后续状态,执行递归的DFS搜索。该方法具有很强的通用性。
在读《挑战程序设计竞赛》时,想到了以前玩的一个小游戏---青蛙交换位置游戏。
游戏说明:
(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<state_t> 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; } |
执行结果如下:
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
1 条留言 访客:0 条 博主:0 条 引用: 1 条
来自外部的引用: 1 条