题目内容

小明在一个足球场上踢球。他需要绕过障碍物把球踢到门里。 足球场用大小为$M*M$的正方形网格表示，其中每个元素可以是空地、障碍物、球或者是球门:

• 小明用字母'$X$'表示，只要他在空地里面，就可以上下左右四个方向移动。

• 空地用字母'$0$'表示，在空地上可以自由行走。

• 障碍物用字母'$1$'表示，意味着不能通行，可能有多个障碍物。

• 足球用字符'$B$' 表示，球场上只有$1$个球。

• 球门用字符'$G$' 表示，球场上只有$1$个球门。

  踢球方式:初始时小明和球可能不相邻，小明首先需要走到球的位置才能开始踢球;当移动到球边(相邻格子)后，然后继续向着球的方向移动，球会被踢到同方向相邻格的位置，即:球移动的方向只能与小明移动的方向相同，一次移动一格。

  注:如果球移动前方会碰到障碍物或者边界，那么此次踢球无效，小明和球的位置均会保持不变。

  举例:小明首先移动到球左侧的相邻格子，然后再向右移动到球当前所在格子(意味 着踢了一脚球)，那么球就会移动到当前格的右侧一格(算作踢球一次)、且只能移动 到右侧格子。如果小明从球下方朝上移动到当前球所在格子，那么球会移动到当前格 的上方一格。

  小明需要持续移动最终把球踢到门所在的格子内。返回小明把球踢到门里需要踢球的最少次数，若无法踢到门中，返回$-1$。

  注意:足球每移动一次算做一次踢球，小明自己移动没有踢球的情况下不算踢球次 数。

输入描述

输入第一行输入一个正整数$M(5<=M<=20)$。

接下来输入$1$个$M*M$的矩阵,一共M行，每行$M$个字符。

数组的行列M 取值范围5$<=m<=20$

数组中仅包含字符'$0$'，'$1$','$B$','$G$',以及'$X$'。

数组中'$X$'，'$B$'和'$G$'各只能出现一个。。

输出描述

返回小明把球踢到门中需要踢球的最少次数

样例1

输入

5
0 0 0 0 0
0 0 0 0 G
0 0 B 0 0
X 1 0 0 0
0 0 0 0 0

输出

3

说明

小明把球踢到门里最少需要踢$3$次球。

样例2

输入

5
0 0 0 0 0
0 0 0 0 G
1 0 B 0 0
X 1 0 0 0
1 0 0 0 0

输出

-1

说明

小明无法把球踢到门里