P1649 [USACO07OCT] Obstacle Course S

题目描述

在 $N \times N$ 方格中，x 表示不能行走的格子，. 表示可以行走的格子。

只可以上下左右四个方向行走，并且不能走出这些格子之外。开始和结束时的方向可以任意。

现在要从 A 点走到 B 点，请问最少要转 90 度弯多少次？

输入格式

第一行一个整数 $N(1 \le N \le 100 )$

下面 $N$ 行，每行 $N$ 个字符，只出现字符： . 、 x 、 A 、B，每个字符后有一个空格。

输出格式

一个整数：最少转弯次数。

如果不能到达，输出 -1。

输入输出样例

输入

3
. x A
. . .
B x .

输出

2