• [1719] Wc的朗利特树篱迷宫(Ⅱ)

  • 时间限制: 1000 ms　内存限制: 65535 K
  • 问题描述

  • Wc还在放暑假，这次他和他的麻瓜朋友们一起去英国的威尔特郡，参观朗利特树篱迷宫。WC为了增加迷宫的乐趣，特意给迷宫施加了一个随机魔法，每次进入迷宫时，迷宫都会重新规划，但可以肯定的是迷宫一定只有一个起点和至少一个终点。现在给你几个迷宫，让你判断一下WC和他的麻瓜朋友们能否走出迷宫，如果能，就输出走出迷宫的最少步数，否则输出-1。由于朋友比较麻瓜，他们只会朝上下左右四个方向走。


    ‘S’ 表示起点

    ‘E’ 表示终点

    ‘*’ 表示路，可以走

    ‘#’ 表示墙，不能行走


  • 输入
  • 第一行为一个正整数T，表示接下来又T个迷宫
    对于每个迷宫，第一行为一个正整数n，表示迷宫的长和宽，(1<=n<=100)
    接下来会有n行，每行仅由‘S’、‘E’、’*’、’#’组成，表示迷宫。
  • 输出
  • 对于每个迷宫，如果可以从起点到终点，则输出最少步数，否则输出-1。
  • 样例输入
  • 2
5
S****
*****
*****
*****
****E
5
S***#
***#*
**#**
*#***
#***E
  • 样例输出
  • 8
-1
  • 提示
  • 无
  • 来源
  • 本站或者转载
  • 操作

显示春菜