|
|
马上注册，结交更多好友，享用更多功能^_^
您需要 登录 才可以下载或查看，没有账号？立即注册
x
题目描述：
ID为TMao的淘宝用户前些日子在淘宝机器人网店购买了一个智能机器人oz.这个机器人不仅精致小巧，还具有很多有意思的功能。比如：oz可以在迷宫里自由的上下左右走动; 并且，在不碰到障碍物的情况下，它能够以最短时间从入口处走到出口 (假设存在的话); 最智能的是，在有充电器的地方oz还可以给自己充电 (^_^)。
现在，TMao设计了很多种迷宫，并且在里面随意的摆了些充电器，想请你们帮他算下，这个智能机器人要多久时间可以走出去呢？
他做了如下假设：
1.迷宫可以看作是长为w，宽为h的网格；
2.机器人每移动一步，需要时间1s，消耗电量0.5格；
3.机器人初始电量为满格4格；
4.每个充电器充电次数不限 (充电时间所需时间忽略不计)，机器人可以反复经过一个地方，但是不能走到有障碍的地方,并且一旦机器人电量变为0,它就只能停下来，哪怕这个位置正好有充电器，它也没有足够的电量去执行充电操作；
5.机器人走到迷宫出口，必须至少还有0.5格电量，否则也算没走出出口。
输入：
输入有多组测试案例，每个测试案例以如下形式输入。第一行输入w,h分别表示迷宫的长和宽，当输入0 0时结束输入（w , h <= 10）。
接下来的h行表示迷宫的布局：-1表示该位置是障碍物, 0表示该位置什么也没有,1表示迷宫入口, 2表示迷宫出口, 3表示该位置有充电器。
输出：
对应每个测试案例，输出机器人oz走到出口处的时间;如果无法按要求走到出口则输出”Pity oz!”。
样例输入：
4 3
2 0 0 0
0 0 0 0
0 0 0 1
4 3
2 -1 0 0
-1 0 0 0
3 0 0 1
0 0
样例输出：
5
Pity oz!
|
|
[复制链接]
( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)
狗仔卡
发表于 2013-12-22 15:33:35
置顶卡
千斤顶
显身卡
发表于 2013-12-22 15:35:06
发表于 2013-12-22 16:21:47