Description

The tank in Planet $X$ is very strange. It must cross positive-energy radiation zones and negative-energy radiation zones alternately to keep running normally; otherwise, it will be scrapped.

A tank needs to go from zone $A$ to zone $B$ (zones $A$ and $B$ themselves are safe zones, with neither positive-energy nor negative-energy properties). How should it move to make the path as short as possible?

The known map is a square grid. The grid marks zones $A$ and $B$ with letters. All other zones are marked with a plus sign or a minus sign, representing positive-energy and negative-energy radiation zones, respectively.

For example:

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

The tank can only move to an adjacent zone horizontally or vertically.

Input Format

The first line contains an integer $n$, representing the size of the square grid, $4 \le n<100$.

The next $n$ lines each contain $n$ entries, each being one of A, B, +, -, separated by spaces.

Output Format

Output an integer representing the minimum number of moves for the tank to get from zone $A$ to zone $B$.

If there is no solution, output $-1$.

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

10

Hint

Time limit: 1 second, 512 MB. Lanqiao Cup, 2015, 6th National Finals.

Translated by ChatGPT 5