#P1735. 字母迷宫【数据有误待修复】

字母迷宫【数据有误待修复】

题目背景

数据疑似有误。

题目描述

打败了 DIABLO,Mini 进入了迷宫。这是个奇怪的迷宫,迷宫的每一个地点要么有一个用来传送的门,要么是障碍。Mini 现在站在迷宫的原点处,但是眼看远在 (N,N)(N,N) 的公主就要被转移,Mini 心情焦急万分,为了能最快地到达公主处救出公主,Mini 希望能走一条最快的路径。注意,Mini 可以把迷宫的 (1,1)(1,1)(1,N)(1,N)(N,1)(N,1) 处当作原点。

迷宫里,某些地点会有门,将门激活,Mini 就会被传送到某个地点,当然,魔王 Bill 只创造了三种门,所以迷宫里最多有就只有三种门,而且在这个迷宫中要到达下一个点必须通过门。。(什么逻辑 TUT。。)

在迷宫中,可能会遇到的三种门分别如下:

  • 时空之门,Mini 可以往上下左右四个方向中的任意一个方向传送一格;
  • 海洋之门,Mini 可以往上下左右四个方向中的任意一个方向传送两格;
  • 天堂之门,Mini 需要停留一步,聚气,然后可以往左上左下右上右下四个方向中的任意一个方向传送一格。

当然,使用每一个门都算作一步。

当然还有障碍,如果有障碍,那么这个点没有门且这个点不能被传送到。

但是,魔王 Bill 有可能创造出了一个完全无法到达 (N,N)(N,N) 的迷宫,所以,当从三个原点出发都无法到达 (N,N)(N,N) 时,请输出 No answer。注意,原点算作一步(Mini 一开始站在 (1,1)(1,1)(1,N)(1,N)(N,1)(N,1) 的位置,然后走一步到原点,所以原点算作一步)。

输入格式

第一行一个数 NN,表示迷宫的大小 N×NN\times N

以下 NN 行,每行 NN 个字符,表示迷宫的示意图。字符要么是字母 ABC,要么是障碍。

A 表示时空之门,B 表示海洋之门,C 表示天堂之门,障碍用 * 表示。

输出格式

输出为 Mini 从原点处走到公主处的最快路径长度。无解输出 No answer

3
A*C
*AC
ACA
No answer
3
AAA
CAA
AAA
3

提示

对于 100%100\% 的数据,0N12000\le N\le 1200