P8628 [Lanqiao Cup 2015 National AC] Crossing the Minefield

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.

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

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$.

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