PID181 / 字母迷宫
题目描述

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

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

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

时空之门,Mini可以往上下左右四个方向中的任意一个方向传送一格。

海洋之门,Mini可以往上下左右四个方向中的任意一个方向传送两格。

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

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

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

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

输入格式

第一行一个数N,表示迷宫的大小(N*N)(0<=N<=1400)

以下N行,每行N个字符,表示迷宫的示意图。字符要么是字母ABC,要么是障碍。A表示时空之门,B表示海洋之门,C表示天堂之门,障碍用*表示。

输出格式

为Mini从原点处走到公主处的最短路径(最短路径不一定消耗步数最少)所消耗的步数(若有多条最短路径则输出消耗步数最少的那个)。无解输出“No answer”(引号不输出)

样例输入
样例输出
提交题目 Error [ 更改语言 ] Language
C C++ Pascal Python2
相关讨论
查看更多讨论
发布新讨论 讨论