#1025. 不喜欢拐弯 1

不喜欢拐弯 1

题目描述

一个 N×N 的棋盘,你要从起点走到终点,只能向上、下、左、右行走,不能走出棋盘外。每个格子要么是黑色,要么是白色。你不喜欢黑色,所以你绝不会踏入黑格子。你也不喜欢拐弯,但你有时却不得不拐。问:你在途中最少拐弯多少次?

注:在起点处你可以任选一个方向开始行走,不计入拐弯次数。

输入格式

第一行:一个整数 N

接下来是一个 N×N 的字符矩阵,只包括四种字符:.,x,A,B,其中 . 表示白格子,x 表示黑格子,A 表示起点,B 表示终点。

输出格式

一个整数:最少拐弯次数。如果不能到达,输出-1。

样例输入

3
.xA
...
Bx.

样例输出

2

数据范围

2<=N<=100