题目描述

芯芯被困在一个 N × M 的迷宫中，她需要尽快逃离迷宫。迷宫由 .（空地）和 #（障碍物）组成，此外，迷宫的边界一定是墙（#）。芯芯可以在空地上移动，每次可以向 上、下、左、右 四个方向移动 一步，但不能穿越墙壁与障碍物。

请你计算小芯从起点 S 逃到终点 E 的最短步数。如果无法到达终点，则输出 -1。

输入格式

• 第一行包含两个整数 N 和 M（2 ≤ N, M ≤ 100），表示迷宫的大小。
• 接下来 N 行，每行 M 个字符，表示迷宫的地图：
  • S 表示小芯的起始位置（唯一）。
  • E 表示出口（唯一）。
  • . 表示空地，可以通过。
  • # 表示障碍物，不可通过。

输出格式

• 输出一个整数，表示小芯从 S 到 E 的最短步数。如果无法到达出口，则输出 -1。

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

5

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

-1

6 7
#######
#S...E#
###.#.#
#.....#
#.#.###
#######

4

说明

• 样例 1：小芯有一条畅通无阻的路径可以到达 E，最短路径长度为 5。
• 样例 2：E 被墙包围，无法到达，因此输出 -1。
• 样例 3：S 到 E 有两条可行路径，其中一条较短，最短路径长度为 4。

提示

• 迷宫边界始终是墙（#），S 和 E 不会在边界上。