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

输入 #1

3
. x A
. . .
B x .

输出 #1

2

说明/提示

【样例 $1$ 解释】

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