A8041.地下城主

普及/提高-

官方

通过率:0%

时间限制:1.00s

内存限制:128MB

题目描述

这题是一个三维的迷宫题目,其中用‘.’表示空地,‘#’表示障碍物,‘S’表示起点,‘E’表示终点,求从起点到终点的最小移动次数,解法和二维的类似,只是在行动时除了东南西北移动外还多了上下。可以上下左右前后移动,每次都只能移到相邻的空位,每次需要花费一分钟,求从起点到终点最少要多久。

输入格式

前三个数,分别表示层数、一个面的长和宽,后面是每层的平面图。

输出格式

最小移动次数。

输入输出样例

  • 输入#1

    3 4 5
    S....
    .###.
    .##..
    ###.#
    #####
    #####
    ##.##
    ##...
    #####
    #####
    #.###
    ####E

    输出#1

    Escaped in 11 minute(s).
  • 输入#2

    1 3 3
    S##
    #E#
    ###

    输出#2

    Trapped!

说明/提示

对于题目给出数据的含义就是输入 l,r,c(1l,r,c100)l,r,c(1 \leq l,r,c \leq 100),分别代表迷宫有 ll 层,每层长宽分别是 crc,r。对于数据以可以这样移动:

(1,1,1)>(1,1,2)>(1,1,3)>(1,1,4)>(1,1,5)>(1,2,5)>(1,3,5)>(1,3,4)>(1,4,4)>(2,4,4)>(2,4,5)>(3,4,,5)(1,1,1)->(1,1,2)->(1,1,3)->(1,1,4)->(1,1,5)->(1,2,5)->(1,3,5)->(1,3,4)->(1,4,4)->(2,4,4)->(2,4,5)->(3,4,,5)

1111 步就可以到达终点 对于数据二明显不能到达,则输出 Trapped!Trapped!

这题用 BFSBFS 解,每次去队首元素,如果是终点则输出结果移动的次数,否则,从该点开始分别向东南西北上下移动(如果可以走的话)并继续搜,如果到队列为空还没搜到解法,则说明无解。

首页