JB班机器人大赛
Description
JB班为丰富同学们的课余生活,举办了一场机器人大赛。要求在一块场地中,从指定的起点start到达(只要行驶路线经过即算到达,不一定要停下)指定的终点goal. 场地划分为个方块,方块有四种类型(0.空地 1.障碍物 2.起点 3.终点) 但由于小明拙劣的技术水平,他造出来的机器人有以下两个缺陷:1.只能在静止时转向(即行驶时只能一直往前走) 2.没有刹车系统(会一直行驶直到遇到障碍物)。
粗略流程:1.当机器人启动时,它不能直面障碍物(即前进方向上的障碍物不能紧挨着它) 2.机器人遇到障碍物停下(停在障碍物的前面)后,机器人面前的障碍物会被清除。机器人此时可以重新转向,亦可以不转向。 3.当机器人重新启动时,它不能直面障碍物(即前进方向上的障碍物不能紧挨着它)
比赛规则如下:1.一次直线行驶记为1步(step) 2.超过十步还没有到达记为比赛失败,十步以内(包括)记为比赛成功 3.机器人冲出赛道记为比赛失败。
现请问题求解能力高超的你来确定小明是否有一种控制策略使比赛成功,若能成功,请输出最小步数,若不能成功,请输出-1.
Input
每个测试文件包含若干测试样例(样例数<=100) 每个测试文件的结尾以两个整数0标记。
对于每个测试样例:
第一行包含两个整数M,N[**请注意M,N的顺序**]. (1<=N<=20, 2<=M<=20)
接下来会有n行,每行包含m个整数. 每个整数的含义如下:0表示空地 1表示障碍物 2表示起点 3表示终点
Output
对于每个测试样例,输出一个整数。如果比赛成功,输出最小步数,如果比赛不能成功,输出-1
Sample Input
Sample Output
Hint
POJ 3009
信息
- 难度
- 9
- 分类
- (无)
- 标签
- (无)
- 递交数
- 13
- 已通过
- 2
- 通过率
- 15%
- 上传者