首页 > 其他 > 详细

bfs

时间:2017-08-19 12:19:59      阅读:245      评论:0      收藏:0      [点我收藏+]

有一天陈世进约了唐威豪去看电影,电影院有一个活动,给你一个10*10的矩阵,每一个格子上都有一个0-9的整数,表示一共十种优惠券中的一种。

观众从左上角的格子开始走,走到右下角。每走到一个有着a号优惠券的格子,都必须要玩一个a分钟的游戏来领取这张优惠券。

每次只能向右或向下走。当走到右下角的时候,如果集齐10种优惠券就可以半价看电影呢。

为了能在唐威豪面前展示自己的才智,陈世进准备用最少的时间领取全部的优惠券(他要省出最多的时间陪唐威豪)。聪明的你能告诉陈世进,他最少要花费的时间是多少?

Input

输入包含10行,每行10个数字,以空格隔开,表示格子上的优惠券的种类。数据保证存在合法路径。

Output

输出陈世进走到右下角的最小时间花费。

Sample Input

0 1 2 3 4 5 6 7 8 9
1 1 1 1 1 1 1 1 1 0
2 1 1 1 1 1 1 1 1 0
3 1 1 1 1 1 1 1 1 0
4 1 1 1 1 1 1 1 1 0
5 1 1 1 1 1 1 1 1 0
6 1 1 1 1 1 1 1 1 0
7 1 1 1 1 1 1 1 1 0
8 1 1 1 1 1 1 1 1 0
9 1 1 1 1 1 1 1 1 5

Sample Output

50

bfs

原文:http://www.cnblogs.com/carry-2017/p/7395946.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!