qq_36424540 2017-08-02 11:19 采纳率: 87.5%
浏览 1012
已采纳

希望大神解答一下,这道题用bfs+优先队列为什么不对,只能用最短路径来写

Bessie and the rest of Farmer John's cows are taking a trip this winter to go skiing. One day Bessie finds herself at the top left corner of an R (1 <= R <= 100) by C (1 <= C <= 100) grid of elevations E (-25 <= E <= 25). In order to join FJ and the other cows at a discow party, she must get down to the bottom right corner as quickly as she can by travelling only north, south, east, and west.

Bessie starts out travelling at a initial speed V (1 <= V <= 1,000,000). She has discovered a remarkable relationship between her speed and her elevation change. When Bessie moves from a location of height A to an adjacent location of eight B, her speed is multiplied by the number 2^(A-B). The time it takes Bessie to travel from a location to an adjacent location is the reciprocal of her speed when she is at the first location.

Find the both smallest amount of time it will take Bessie to join her cow friends.

Input
* Line 1: Three space-separated integers: V, R, and C, which respectively represent Bessie's initial velocity and the number of rows and columns in the grid.

* Lines 2..R+1: C integers representing the elevation E of the corresponding location on the grid. 

Output
A single number value, printed to two exactly decimal places: the minimum amount of time that Bessie can take to reach the bottom right corner of the grid.
Sample Input

1 3 3
1 5 3
6 3 5
2 4 3

Sample Output

29.00

Hint
Bessie's best route is:
Start at 1,1 time 0 speed 1
East to 1,2 time 1 speed 1/16
South to 2,2 time 17 speed 1/4
South to 3,2 time 21 speed 1/8
East to 3,3 time 29 speed 1/4

  • 写回答

1条回答 默认 最新

  • devmiao 2017-08-02 16:25
    关注
    本回答被题主选为最佳回答 , 对您是否有帮助呢?
    评论

报告相同问题?

悬赏问题

  • ¥20 收一个快手协议下单算法
  • ¥15 求一个图片中的成交量选股公式
  • ¥15 已知正方形内随机生成坐标matlab
  • ¥30 关于#python#的问题:我想要的是这79个大特征对于房屋售价的最大的影响前十名(相关搜索:随机森林)
  • ¥15 使用matlab计算自定义特殊函数的二重积分,改变积分顺序所得的结果不同的问题?
  • ¥15 mysql做碎片化处理老是报错怎么办
  • ¥15 如何正确在vs2010中初始化map对象
  • ¥30 mmdet3d模型部署问题
  • ¥15 comsol仿真反射率、吸收率时峰值位置和深度不对!
  • ¥30 Visual Studio找不到sdk,如何解决?