3599: 迷宫逃脱

内存限制:128 MB 时间限制:1.000 S
评测方式:文本比较 命题人:
提交:10 解决:5

题目描述

小杨被困在一个 n×m 的迷宫中,他需要逃到出口。

迷宫由以下字符组成:

  • '.':空地,可以通行
  • '#':墙,不能通过
  • 'S':起点(仅一个)
  • 'E':出口(仅一个)

小杨每一步可以向上、下、左、右四个方向移动一格。

请你判断:小杨是否能从起点 S 走到出口 E

如果能,输出最短移动步数;如果不能,输出 -1

输入

  • 第一行:两个整数 n 和 m1n,m100),表示迷宫行数和列数
  • 接下来 n 行:每行一个长度为 m 的字符串,表示迷宫地图

输出

一行一个整数:如果能到达出口,输出最短步数;否则输出 -1

样例输入 复制

5 5
.....
.#.#.
.S#E.
.#.#.
.....

样例输出 复制

10