九度Online Judge

OJ新增积分机制,如有任何问题或者建议,请发帖到九度论坛OJ意见反馈版,祝大家一切顺利!
亲,九度OJ官方微博开通了,欢迎你来粉!微博地址:weibo.com/jobdu

 题目1404-九度Online Judge,用代码记录你的成长之路!

题目1404:机器人网店

时间限制:1 秒

内存限制:32 兆

特殊判题:

提交:429

解决:99

题目描述:

         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!