I : 冰壶

Progress Bar

时间限制:1 Sec 内存限制:0 MiB
提交:16 答案正确:2

提交


题目描述

近年来冰壶运动越来越受欢迎。比赛在冰板上进行,冰板是一个矩形的网格。玩家只使用一个冰壶。比赛的


目的是用最少次数的敲击把冰壶从一开始到另一个目标。图1示出了示例。有些方块可能是石块(障碍,用1代表)。


有两个特殊的方块,即起点和终点,分别用2和3表示。为了使冰壶达到目标,你可能不得不让冰壶撞向石块,之后


石块破碎,冰壶停留在前一格(滑动方向的前一格),然后再次选择方向对冰壶进行敲击,使它继续滑动。


    冰壶的运动遵循以下规则:


    1:起初,冰壶位于起点(地图上的数字2)。


    2:冰壶的移动限于x轴和y轴方向。禁止对角线方向移动。


    3:当冰壶静止时,你可以通过敲击使它移动。但是移动的方向有限制,如果选择的方向相邻就是障碍,即


敲击后停留在原地,那么这种方向就是不合法的(图2(a))。


    4:一旦击打进行滑动,冰壶一直向同一方向移动,直到发生下列情况之一:


    (1)击中一个石块,石块破碎消失。(冰壶停留在石块前一格)(图2(b),(c))。


    (2)冰壶停在终点3.(终点是一块很粗糙的地方,冰壶滑到此处不会再滑动)。


    (3)冰壶没有受到阻碍,一直滑动向了界外。发生这种情况,比赛失败。


    5:不能在游戏中击打冰壶10次以上。如果击打10次仍然没有到达目的地,比赛就以失败而结束。


    根据这些规则,你需要判断冰壶能否到达终点,如果不能到达目标,输出-1;如果能到达,输出到达目标最小的


击打次数。图中给出样例的过程。


输入

第一行两个数m和n,分别代表场地的列数和行数,输入以两个0结束。 2 <= m <= 20, 1 <= n <= 20.


接下来n行输入,每行m个,代表场地。(0是冰面,1是石块,2是起点,3是重点)。


输出

如果不能到达目标,输出-1;如果能到达,输出到达目标最小的击打次数。


样例输入

复制
2 1
3 2
6 6
1 0 0 2 1 0
1 1 0 0 0 0
0 0 0 0 0 3
0 0 0 0 0 0
1 0 0 0 0 1
0 1 1 1 1 1
6 1
1 1 2 1 1 3
6 1
1 0 2 1 1 3
12 1
2 0 1 1 1 1 1 1 1 1 1 3
13 1
2 0 1 1 1 1 1 1 1 1 1 1 3
0 0

样例输出

复制
1
4
-1
4
10
-1

提示


			

来源