P1735 Letter Maze

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

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 the length of the fastest path for Mini to reach the princess from the chosen origin. If there is no solution, output `No answer`.

For $100\%$ of the testdata, $0 \le N \le 1200$. Translated by ChatGPT 5