← 返回比赛

已结束 GESP挑战赛#31

← 上一题下一题 →

A7359 | $小午历险记之沙漠信标$

时间限制1s

内存限制128MB

通过 / 提交0/0

题目描述

在一片被风沙覆盖的无人区中，有一张由方格组成的探测区域图。小午需要从起点 $S$ 出发，前往目标信标 $T$。 地图中每个字符的含义如下： - . ：普通沙地，可以通行； - # ：岩壁，无法通过； - G ：能量检查点； - S ：起点； - T ：终点。 小午每一步可以向上 / 下 / 左 / 右移动一格（不能走出地图范围）。在整个行进过程中，最多只能通过一次能量检查点：也就是说，路径上最多进入 $1$ 个 G 格子；进入该格子的那一步同样计入步数。 请计算从 S 到 T 的最少步数；如果无法到达，输出 -1 。

输入格式

第一行包含两个整数 $n, m$。 接下来 $n$ 行，每行一个长度为 $m$ 的字符串，表示探测区域地图。 保证地图中恰好有一个 S 和一个 T 。

输出格式

输出一个整数，表示最少步数；若无法到达，则输出 -1 。

输入输出样例

输入 #1

3 5
S..#.
...GT
...#.

输出 #1

C++ 编辑器

输入

输出