返回小组 开始 2026-05-10 09:07:00

测试

结束 2026-05-10 12:00:00
Contest is over.
当前 2026-05-23 17:01:42

E. 走迷宫 Ⅲ

描述

迷宫是一个N \times M ,N行M列的矩阵。玩家需要从初始位置移动到终点位置,移动到相邻(上/下/左/右)的格子视为1步,求最小移动步数。

'.'表示是一个空格,迷宫可以站人

'#'表示是迷宫的墙/障碍物,不能站人

'S'表示玩家初始位置(可以站人)

'E'表示玩家需要抵达的终点位置(可以站人)

输入

第一行两个数字N,M

下面N行,每行M个字符,描述迷宫每格的状态

输出

仅一个数字,表示玩家从初始位置到达终点位置的最少步数。

如果无法到达,那么输出-1

样例

输入

10 8
########
#.#.##.#
#.#..#.#
##....##
#.#.#S.#
#.#...##
#.#....#
#E##.#.#
###..#.#
########

输出

-1

输入

7 10
##########
#.......##
#.####..##
#....##.##
###...#..#
#S...##.E#
##########

输出

19

提示

N,M \leq 2000 保证迷宫的最外围都是墙


Submit

登录

注册
时间限制 1 秒
内存限制 128 MB
提交