广度优先搜索和双向广度优先搜索求解Matrix67的迷宫问题的C语言实现

问题描述见 http://weibo.com/1915548291/z4eTPtAnv
简单来说,就是一个小迷宫。可以重复走,但是不能倒退。经过每条边都意味着执行一次运算,现在要2011从迷宫口进去,2012从迷宫口出来。
一个思想就是广度优先搜索,能够找到最短的路径。如果对每个状态标记祖先,就能回溯找到完整路径。自己实现了一个简单的Hash,因为最终步数并不多,所以对Hash的要求也不高。
之后又在广度优先搜索的基础上进行修改,实现了双向广度优先搜索。一个点从入口开始搜,一个点从出口开始搜。需要注意的是从出口开始搜的话,所有运算都是相反的。搜的时候会有两个队列,直到两边“碰头”为止。
测试结果中可以看到,双向广度优先搜索明显更快一些。
马上光棍节了,几个常量都定义的全是1,哈哈。

Continue reading »