SEA402 迷宫最短通行

难度梯度：T3-｜训练重点：网格 BFS 最短路

题目描述

N×M 的地图中，S 为起点，E 为终点，. 可走，# 为障碍。每步可上下左右移动一格，求从 S 到 E 的最少步数，不可达输出 -1。

S、E 都视为可通行格；走过它们均不需额外代价。允许重复经过可通行格，但求最少步数。

输入格式

第一行 N M，接下来 N 行地图。保证恰有一个 S 和一个 E。

输出格式

输出最少步数或 -1。

样例输入

3 4
S...
##.#
...E

样例输出

5

样例说明

路线沿第一行到第 3 列，再向下两步、向右一步，共 5 步。

数据范围

1≤N,M≤500；N×M≤2×10^5。

子任务

30 分：N,M≤30；70 分：无附加限制。