UVa 10047

The Monocycle

from Volume 2. Data Structures :: Graphs

Description

一个环被五等分，分别染上不同的颜色。在一个地图中，每次移动一格，环就会滚动五分之一。环刚开始时面朝北，绿色向下。每次转向90度或者滚一格都必须花费一秒钟。走到终点时，必须同样绿色朝下，才算达到目的，但是方向可以任意。输入地图的，地图上标记了可以通过和不可以通过的点，还有起点和终点。输出最少花费时间，能够从起点走到终点。

Solution

更加严谨的 BFS ，做这题可以对 BFS 了解更进一步。

• BFS 的队列应该是一个优先队列，所以要去维护队列的优先性。
• 判断到达目的地的时候，应该是判断队头元素，而非刚刚搜到的新状态。
• 应该用一个 visit 数组存储处于某状态时的最优值，而非是否已有这个状态。这个状态。_