填空题

迷宫难题

Question

图森未来的自动驾驶小卡车今天被派到了一个陌生的迷宫内部运输一些货物。

工程师小图已经提前拿到了这个迷宫的地图，地图是一个n*m的字符矩阵，上面包含四种不同的字符："."，"#"，"S"和"E"。其中"S"和"E"分别代表运货的起点和终点，"."为可行驶区域，"#"为不可行驶区域。每个可行驶区域都可以移动到上、下、左、右相邻的可行驶区域，且四种移动的距离都为1。

为了估算运输的成本，小图希望你可以帮助他计算从起点到终点的最短行驶距离。

例如，对于下方的输入样例1，从起点到终点有且仅有一条路径，路径的长度为15（最开始卡车在S的位置，需要经过15次移动才能到达E的位置）。所以，最短行驶距离也为15。

而输入样例2，因为多出了一条直接从S到E的路径，所以最短行驶距离会减少到7。
输入描述： 第一行有两个正整数，分别为n和m（2 <= n, m <= 1000），为数据的行数和列数。

接下来的n行，每行包含m个字符，构成了整张地图。地图中只包含"."，"#"，"S"和"E"四种字符，且"S"和"E"都会且仅会出现一次。输入样例： 6 10 ########## #........# #.######.# #.######.# #.######.# #S######E# 输出描述： 输出一个正整数，为从起点到终点最短行驶距离的长度。输出样例 15