#4119. 逃出实验室

逃出实验室

题目名称:逃出实验室

【题目描述】

人工智能实验室因系统故障被锁死,少年小启被困在了实验舱内。实验舱被划分为一个 M × N 的矩形区域,每个格子表示一个位置:

  • 'S':小启的位置(起点);
  • 'E':逃生门的位置(终点);
  • '.':可以安全行走的通道;
  • '#':被封死的舱门,无法通过。

每次小启只能向上、下、左、右四个方向移动一格。你能帮他找到一条最短路径逃出去吗?


【输入格式】

第一行输入两个正整数 MN(1 ≤ M, N ≤ 15),表示实验室的行数与列数。 接下来的 M 行,每行包含 N 个字符,表示实验室的地图布局。

地图中保证只有一个起点 'S' 和一个终点 'E'


【输出格式】

输出一个整数,表示从起点 S 到终点 E 至少需要经过的方格数(包含起点和终点)。

如果无法到达终点,输出 -1


【输入样例】

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

【输出样例】

18