POJ 2251 Dungeon Master

题意

给出一个三维迷宫,上下左右前后六联通的走法,给你起点和终点,要你求从起点到终点的最少步数。

思路

拿到问题,首先发现是在一个迷宫里面进行,联通方向有六个,求最短路,且数据规模较小,这些都是适用于BFS解题的特征。接下来的关键就是正确地实现BFS了,对BFS的实作原理不太理解的话,不妨先思考在一棵树上遍历时的BFS的实作过程。在BFS的实现过程中,需要正确地判断某个点是不是有效,需要在正确的时机打访问标记,需要正确地操作队列,注意这三点一般不会产生问题。本题并不需要我们实现图结构,因为迷宫本身就已经可以看成图了。在BFS过程中,因为搜索完当前深度的全部状态,才会取出更大深度的状态,所以在BFS过程中,只要我们进入了表示走到终点的状态,就无需再考虑其他状态了,因为即使其他状态也能表示到达终点,其深度(步数)也一定不会比第一个到达的状态少,这样可以节省一些时间。还有一些诸如“连通向量”等小技巧,可以减轻编码负担。

代码

 

1 Comment

  1. […] POJ 2251 Dungeon Master […]

    Reply

Leave a Reply

Scroll to top