Description

After defeating DIABLO, Mini enters a maze. This is a strange maze where every cell either has a teleporting door or is an obstacle. Mini now stands at the origin of the maze, but seeing that the princess far away at $(N,N)$ is about to be moved, Mini is extremely anxious and wants to take the fastest route to reach her. Note that Mini may treat $(1,1)$ or $(1,N)$ or $(N,1)$ as the origin.

In the maze, some cells have doors. When a door is activated, Mini will be teleported to another cell. Bill, the demon king, created only three kinds of doors, so there are at most three types of doors in the maze. In this maze, every move to the next cell must be made by using a door.

The three types of doors are as follows:

• Spacetime Door: Mini can teleport one cell in any of the four directions: up, down, left, or right.
• Ocean Door: Mini can teleport two cells in any of the four orthogonal directions.
• Heaven Door: Mini needs to stay for one step to charge, then can teleport one cell in any of the four diagonal directions: up-left, down-left, up-right, or down-right.

Using any door counts as one step.

There are also obstacles. If a cell has an obstacle, then that cell has no door and cannot be teleported onto.

However, Bill may have created a maze where $(N,N)$ is completely unreachable. Therefore, if starting from all three origins still cannot reach $(N,N)$, please output No answer. Note that the origin counts as one step (Mini starts at $(1,1)$ or $(1,N)$ or $(N,1)$, then takes one step to the origin, so the origin counts as one step).

Input Format

The first line contains an integer $N$, denoting the size $N \times N$ of the maze.

The next $N$ lines each contain $N$ characters describing the maze. Each character is either a letter among A, B, C, or an obstacle.

A denotes a Spacetime Door, B denotes an Ocean Door, C denotes a Heaven Door, and an obstacle is denoted by *.

Output Format

Output the length of the fastest path for Mini to reach the princess from the chosen origin. If there is no solution, output No answer.

3
A*C
*AC
ACA

No answer

3
AAA
CAA
AAA

3

Hint

For $100\%$ of the testdata, $0 \le N \le 1200$.

Translated by ChatGPT 5