[USACO07OCT] 障碍路线Obstacle Course

这道题可以用一个特殊的BFS来求解。每次把队首元素四个方向上的点扩展到队尾,用桶来记录转弯次数。

1.初始状态

A(起点)的转弯次数为-1。

2.产生结点的规则

现在,起点位于队首。

从队首的点向四周逐“层”扩展,每一“层”扩展到的新点入队列,这些新点显然不需要转弯就可以达到(起点任意方向),所以他们的转弯次数记录为0 (也就是起点+1,你的疑问马上就会得到解答)

这就是产生新结点的策略。

3.记录每个点的转弯次数

扩展到的新点的转弯次数=队首点的转弯次数+1。(由于BFS的特点,新点未被访问过才可以被加入队尾)

下面是证明。

如果扩展到的新点是不转90°(直走)就可以到的,那该点一定被扩展了队首点的点(队首点的父结点,不知道这么说对不对)访问过,此时该点不会被当作新点处理。同理,转弯180°的点也一定被扩展了队首点的点访问过。

所以,扩展到的新点一定是转弯90°(左或右)才能走到的。

此时,到新点的转弯次数=队首点的转弯次数+1。

证明完毕。

 

 

发表评论

邮箱地址不会被公开。 必填项已用*标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据