A-A+

深度优先搜索求解青蛙交换位置小游戏

2014年04月20日 算法 评论 1 条 阅读 1,145 次
摘要:

用DFS搜索算法求解青蛙交换位置游戏。详细描述了算法的步骤和代码结构,包括描述状态的表示,获取后续状态,执行递归的DFS搜索。该方法具有很强的通用性。

在读《挑战程序设计竞赛》时,想到了以前玩的一个小游戏---青蛙交换位置游戏

frog

游戏说明:

(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进行搜索。

搜索框架也是非常确定的结构。

好了,就这三步,是不是很简单?

完整的代码大约只有100多行,本文罗列如下。

执行结果如下:

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 条

  • 《挑战程序设计竞赛》读书笔记 | 薛途的博客 | 薛途的博客

给我留言