logo AlgoBeat OnlineJudge 返回比赛
登录 注册

C. [ABSEC0002] 迷宫通行

内存限制:512 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较

题目描述

给定一个 的网格迷宫,S 表示起点,E 表示终点,. 表示可以通行的空地,# 表示不可通行的墙壁。

每次只能向上下左右四个正方向移动一格。请你求出从起点走到终点的最短步数。如果无法到达终点,请输出 -1

输入格式

第一行包含两个整数 ()。

接下来的 行,每行包含一个长度为 的字符串,表示迷宫地图。

保证起点 S 和终点 E 在地图中各自恰好出现一次。

输出格式

输出一个整数,表示最短步数。如果无法到达,输出 -1

样例

样例输入 1

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

样例输出 1

5

样例解释

一条可行的最短路径为:

起点 (1,1) (1,2) (1,3) (2,3) (3,3) 终点 (3,4)

共经过 5 步到达终点。