Alternating Energy Tank Path

A strange tank on a distant $X$ star must traverse alternating zones of positive and negative energy radiation in order to function properly. The tank needs to travel from region $A$ to region $B$. Both $A$ and $B$ are safe zones (i.e. have no energy characteristics), while the other cells in the grid are labeled with either a + (representing a positive energy zone) or a - (representing a negative energy zone).

The tank can move horizontally or vertically to adjacent cells. If the tank moves from a safe zone (either $A$ or $B$) into an energy zone, it can choose any energy type to start with. However, if it goes from one energy zone to another consecutively, the sign must alternate. That is, if the previous energy zone was $+$, then the next energy zone must be $-$, and vice versa. Moving from an energy zone to a safe zone is always allowed and resets the alternating requirement.

Your task is to determine the minimum number of moves required for the tank to travel from $A$ to $B$ while obeying the alternating energy requirement. If there is no valid path, output -1.

Note: In the grid, $A$ and $B$ appear exactly once, and the grid is a square matrix.

The formulas used in this description are in LaTeX format. For example, the positive energy is denoted as $+$ and the negative energy as $-$, and the requirement is that the sequence of traversed energy zones (ignoring safe zones) must be in the form $$+,-,+,-,\ldots$$ or $$-,+, -,+,\ldots$$

inputFormat

The first line contains an integer $N$ representing the size of the grid. Following that are $N$ lines, each containing $N$ tokens separated by spaces. Each token is one of the following:

• A: the starting safe zone
• B: the destination safe zone
• +: a positive energy zone
• -: a negative energy zone

You can assume that there is exactly one A and one B in the grid.

outputFormat

Output a single integer: the minimum number of moves required to travel from A to B while following the alternating energy rule. If no valid path exists, output -1.

sample

5
A + - + -
- + - - +
- + + + -
+ - + - +
B + - + -

11