P1649 [USACO07OCT] Obstacle Course S

有一个 $N \times N(1 \le N \le 100)$ 的场地，场地由 $N^2$ 个 $1 \times 1$ 的方格组成。部分方格对于奶牛来说是无法通过的，用 $\texttt x$ 标记出来；其他方格奶牛都可以通过，用 $\texttt .$ 标记出来。 Bessie 发现自己位于这个场地中的位置 $A$，并且她想要移动到位置 $B$ 去舔那里的盐块。像奶牛这种缓慢且笨拙的生物不喜欢转弯，并且只能沿平行于方格边缘的方向移动。 对于给定的场地，求出从 $A$ 到 $B$ 的路径中最少的 $90^{\circ}$ 转弯次数。路径可以从任何方向开始和结束。 如果 Bessie 无法到达盐块的位置 $B$，请输出 `-1`。

第一行一个正整数 $N$，表示场地的长与宽。 接下来 $N$ 行，每行一个长度为 $N$ 的字符串，字符串每个字符为 $\{\texttt{x},\texttt{.},\texttt{A},\texttt{B} \}$ 中的一种，表示该方格的状态。

一行一个整数，表示 Bessie 必须进行的最小转弯次数。

#### 【样例 $1$ 解释】 Bessie 必须至少转弯两次：例如，Bessie 初始面朝南，向南移动一步，然后转身朝西，再向西再移动两步，接着转身朝南，最后向南移动一步进入 $B$ 方格。（按照“上北下南左西右东”理解）