[USACO Oct07]障碍训练场

Grade 0 Open Time Thursday, 21 February 2013, 11:02 pm
Discount 0.8 Time Discount Thursday, 28 February 2013, 11:02 pm
Allow late Yes Close Time Thursday, 28 February 2013, 11:02 pm
Input file obstacle.in Output file obstacle.out

译 By CmYkRgB123

考虑一个 N x N (1 <= N <= 100)的有1个个方格组成的正方形牧场。有些方格是奶牛们不能踏上的,它们被标记为了'x'。例如下图:

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

贝茜发现自己恰好在点A出,她想去B处的盐块添盐。缓慢而且笨拙的动物,比如奶牛,十分讨厌转弯。尽管如此,当然在必要的时候她们还是会转弯的。对于一个给定的牧场,请你计算从A到B最少的转弯次数。开始的时候,贝茜可以使面对任意一个方向。贝茜知道她一定可以到达。

程序名: obstacle

输入

  • 行 1: 一个整数 N
  • 行 2..N + 1: 行 i+1 有 N 个字符 ('.', 'x', 'A', 'B'),表示每个点的状态。

输出

  • 行 1: 一个整数,最少的转弯次数。

输入样例

3
.xA
...
Bx.

输出样例

2