Minimal Turns for Bessie

Bessie the cow is in a square field of size \(N \times N\) (with \(1 \leq N \leq 100\)) composed of \(1\times1\) tiles. Some tiles are impassable (marked with an x). Two special tiles are marked: A (Bessie's starting position) and B (the location of the salt lick).

Bessie can move only in the four cardinal directions (up, right, down, left) and she doesn't like to turn. A turn is defined as a 90° change in direction. Although the path’s length does not matter, you must compute the minimum number of 90° turns required on any valid path from A to B. Bessie may start and finish facing any direction. It is guaranteed that at least one valid path exists.

The problem can be modeled by using a state that keeps track of Bessie's current position and her current moving direction. The cost associated with a state is the number of turns made so far. When moving in the same direction, the cost does not change, but changing direction adds a cost of 1. Solve for the minimum cost to reach cell B from cell A.

inputFormat

The first line contains an integer \(N\), the size of the square field. The following \(N\) lines each contain \(N\) space-separated characters. Each character is one of the following:

• . — an open tile
• x — an impassable tile
• A — Bessie's starting position
• B — the target salt lick location

It is guaranteed that exactly one A and one B exist and that a valid path exists.

outputFormat

Output a single integer representing the minimum number of 90° turns Bessie must make to travel from A to B.

sample

5
. . B x .
. x x A .
. . . x .
. x . . .
. . x . .

6