[Usaco2007 Oct]Obstacle Course 障碍训练课

考虑一个由 $N\times N$ 个方格组成的正方形牧场。贝茜每一步只能移动到与当前方格共边的上、下、左、右相邻方格，不能走出牧场，也不能进入标记为 x 的方格。

牧场中恰有一个标记为 A 的起点和一个标记为 B 的终点。贝茜从 A 出发前往 B。如果连续两步的移动方向不同，则计为一次转弯。开始时贝茜可以面向任意方向，因此第一次移动不计作转弯。

题目保证贝茜一定可以到达 B。请计算她从 A 到达 B 所需的最少转弯次数。

输入格式

第一行输入一个整数 $N$。

接下来 $N$ 行，每行包含 $N$ 个字符。字符可能为 .、x、A 或 B，表示牧场中对应方格的状态。

输出格式

输出一个整数，表示贝茜从 A 到达 B 所需的最少转弯次数。

样例输入

3
.xA
...
Bx.

样例输出

2

数据范围

• $1\le N\le 100$；
• 牧场中恰有一个起点 A 和一个终点 B；
• 保证贝茜可以从 A 到达 B。

来源与许可

本题为 USACO 2007 October 试题「Obstacle Course」，题面与测试数据整理自 BZOJ。

样例 1

输入

3
.xA
...
Bx.

输出

2