题目描述

给定一个由 $1\times1$ 的小方格构成的 $N\times N$ 的网格图，代表一片田地。贝茜在田地中的 $\verb!A!$ 点，想要移动到 $\verb!B!$ 点去舔那里的盐块。其中有一些方格上有障碍物，奶牛不可通行，用 $\verb!x!$ 表示，而可以通行的方格用 $\verb!.!$ 表示。像牛这样的缓慢笨重的生物不喜欢转弯，当然，它们只能沿着和田地边界平行的方向移动。对于给定的田地，请你确定从 $\verb!A!$ 到 $\verb!B!$ 任意路径中最小的 $90$ 度转弯次数。

在开始和结束时，贝茜可以面向任何方向。

. . B x . 
. x x A . 
. . . x . 
. x . . . 
. . x . .

输入格式

第一行一个整数 $N$,下面 $N$ 行，每行 $N$ 个字符，只出现字符：$\verb!.!,\verb!x!,\verb!A!,\verb!B!$，表示上面所说的矩阵格子，每个字符后有一个空格。

输出格式

一个整数：最少转弯次数。如果不能到达，输出 $-1$。

3
. x A
. . .
B x .

2

数据范围

对于全部数据，保证 $2\le N\le 100$。