不做寻常人 2013-07-15 18:47:00
点我顶贴
收藏
删除
首先要根据题意可以构图，将每一个点抽象成东南西北四个点,构造一个三维图。图构造好了就想算法，一开始会觉得是DIJKSTRA，但是有负权边就不可以用。我对Bellman的算法不太了解，但题目中有回路，应该也不行。后发现地图的边长小于30，就可以想到搜索+剪枝来做。这样用一个数组记录出发点到这个点的最大速度，当再次搜到这个点的时候，如果搜到的值大于记录此点的最大速度，就更新记录，并继续向下搜；如果搜到的值小于等于记录此点的最大速度，就停止这次搜索。此外还有一个剪枝:可以在搜到的值小于（记录终点的最大速度+最多可以加的最大速度30），即再次搜索到达起飞点时不可能大于记录终点的最大速度。最后搜完之后比较起飞点四个方向的最大速度就可以了。此外，有很多Oiers不明白为什么连续两次转向要算做调头，因为如果在十字路口的时候，东西南北都有路可以连续两次转向这样就是调头，但是题目叙述中是必须在前，左，右都没路的时候才能调头，这么就会矛盾。所以加有此叙述，实际上连续两次转向是不可能的。
#2 nxyz117@2012-10-21 01:30:00
28668
回复
删除
如果是这种情况呢
E # *100 #
# #
* *
100 100
# *100 #
F
始终转圈 v 一直增加 怎么结束？