Mini's Maze Rescue

After defeating DIABLO, Mini enters a mysterious maze. In this maze, each cell is either an obstacle or contains a teleport door. Mini’s goal is to reach the princess located at ((N,N)) as quickly as possible. She may start from any one of the three starting points: ((1,1)), ((1,N)) or ((N,1)) (note that the starting cell is counted as one step).

There are three types of teleport doors in the maze:

• Time-Space Door: Teleports Mini one cell in any of the four cardinal directions (up, down, left, right) with a cost of 1 step.
• Ocean Door: Teleports Mini two cells in any of the four cardinal directions with a cost of 1 step.
• Heaven Door: Requires Mini to wait a step to gather energy and then teleports her one cell diagonally (i.e. top‐left, top‐right, bottom‐left, bottom‐right), with a cost of 2 steps.

In every non‐obstacle cell there is exactly one door. When using a door, Mini is teleported following the rule of that door and the move cost is added accordingly. Obstacles are denoted by a '#' symbol and cannot be traversed or teleported onto.

Input Format: The maze is given as follows. The first line contains an integer (N) denoting the size of the maze. The next (N) lines each contain (N) tokens separated by spaces. Each token is one of:

• A – representing a Time-Space Door
• B – representing an Ocean Door
• C – representing a Heaven Door
• # – representing an obstacle

Output Format: Output the minimum number of steps required for Mini to reach ((N,N)) from any valid starting position. If none of the three starting positions can reach ((N,N)), output No answer.

inputFormat

The first line contains an integer (N), the size of the maze.\nEach of the next (N) lines contains (N) tokens separated by spaces. Each token is one of: A, B, C, or #.

outputFormat

Output the minimum number of steps required for Mini to reach the princess at ((N,N)). If it is not possible from any of the three starting positions, output No answer.

sample

3
A A A
A A A
A A A

3