题目描述

你开发了一款撞球游戏，游戏区域是一个正方形的网格。网格中有一个球，游戏的目标是以最少的移动次数将球引导到指定位置。

图 $1$ 显示了游戏板的示例。有些网格为空地，有些网格被砖块占据。除此之外，还有两个特殊的网格，即小球的初始位置和目标位置，这两个位置都是空地。一旦小球开始滚动，它将不断滚动，直到撞到一个砖块。为了将小球移动到目标位置，你可能必须将石头砸在一个砖块上，然后再进行下一次滚动。

石头的移动遵循以下规则：

• 一开始，石头就停在起点位置。

• 小球的移动仅限于 $x$ 和 $y$ 方向。禁止对角移动。

• 当小球静止时，你可以使其向某一方向滚动，除非该方向直接靠墙（图$2a$）。

• 一旦开始滚动，小球将不断向同一方向滚动，直到发生以下情况之一：

  • 小球击中一块砖块（图$2b,2c$）。

    • 小球停在它撞到的砖头旁边的空格上。
    • 砖块消失。

  • 小球滚动到整个网格区域以外。

    • 游戏以失败告终。

  • 小球到途径标位置。

    • 小球停在那里，游戏以胜利结束告终。

在一轮游戏中，你滚动小球的次数不能超过 $10$ 次。如果小球在 $10$ 次移动后未达到目标位置，游戏将以失败告终。

按照上述规则规则，我们想知道开始时的小球能否达到目标，如果是的话，还需要最少的移动次数。

在图 $1$ 所示的初始配置中，需要 $4$ 次移动才能将小球从起点带到目标。路线如图 $3a$ 所示。注意，当小球到达目标时，砖头的情况发生了变化，如图 $3b$ 所示。

输入格式

输入是一系列测试数据。输入的结尾由一行 0 0 表示。数据数据得组数不超过 $100$。

每个数据集的格式如下。

板的宽度 $w$ 和高度 $h$，$2≤w≤20,1≤h≤20$。

接下来 $h$ 行每行 $w$ 个数字，描述整个游戏板。

• 0空地
• 1砖块
• 2开始位置
• 3目标位置

输出格式

对于每组数据，输出一个整数，表示从起点到目标位置得最小滚动次数。如果无法在 $10$ 轮之内到达目标，输出-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

提示