给你一个 N×NN \times NN×N 的方格图,# 表示障碍,. 表示没有障碍,可以从一个格子走到相邻的四个格子,但是不能走出这些格子。问从 AAA 点到 BBB 点最少需要转 909090 度的弯几次。
#
.
输入
第一行一个整数 N (2≤N≤100)N \ (2 \leq N \leq 100)N (2≤N≤100)
接下来 NNN 行,每行 NNN 个字符,只出现字符 ., #, A, B。表示上面所说的矩阵格子,每个字符后有一个空格。
A
B
输出
一个整数,表示答案。
如果不能到达,输出 −1-1−1。
样例
3 . # A . . . B # .
2
提示
开始和结束时的方向任意。