丝路最短航路

2026 青少年信息素养大赛 复赛卷五 · 小学组 C++ 第 14 题

题目描述

古代海上丝绸之路，商船从起点港口出发，穿梭在海岛与海域之间。航行地图为 n 行 m 列：

• S：商船起点港口
• E：目标终点港口
• *：可通行安全航线
• .：暗礁海域，无法通行

商船只能向上下左右四个方向航行，每次走一格。求出从起点到终点的最少航行步数；若无法到达终点，输出 -1。

输入格式

第一行两个整数 n, m。接下来 n 行，每行 m 个字符，只包含 S E * .。

输出格式

输出从起点到终点的最短步数，无法到达输出 -1。

样例输入 #1

4 5
S**..
***..
..*E.
.....

样例输出 #1

5

样例输入 #2

4 4
S*..
....
..*E
****

样例输出 #2

-1

数据范围

1 ≤ n, m ≤ 100