题目背景

点我进入原题提交页面

题目描述

给定一个包含 $H$ 行和 $W$ 列的网格。令 $(i,j)$ 表示从上方第 $i$ 行和从左侧第 $j$ 列的单元格。

每个单元格可以是以下之一：起始单元格、目标单元格、空单元格或障碍单元格。

• 是起始单元格当且仅当字符为 S
• 是目标单元格当且仅当字符为 G
• 是空单元格当且仅当字符为 .
• 是障碍单元格当且仅当字符为 #。

保证存在且仅存在一个起始单元格和一个目标单元格。

你当前在起始单元格。你的目标是通过反复移动到与当前单元格相邻的单元格，达到目标单元格。然而，你不能移动到障碍单元格或移动到网格外，并且每次移动必须在垂直和水平之间交替进行。（第一次移动的方向可以任意选择。）

确定是否可以到达目标单元格。如果可以，找出所需的最小移动次数。

输入格式

第一行输入 $H$ 和 $W$

接下来输入一个 $H\times W$ 的字符矩阵。

输出格式

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

3 5
.S#.G
.....
.#...

7

3 5
..#.G
.....
S#...

-1

8 63
...............................................................
..S...#............................#####..#####..#####..####G..
..#...#................................#..#...#......#..#......
..#####..####...####..####..#..#...#####..#...#..#####..#####..
..#...#..#..#...#..#..#..#..#..#...#......#...#..#..........#..
..#...#..#####..####..####..####...#####..#####..#####..#####..
................#.....#........#...............................
................#.....#........#...............................

148

提示

数据范围

• $1\leq\ H,W\ \leq\ 1000$

样例 1 解释

左边图是最佳移动路线只需要 $7$ 步，右边图虽然步数更少，但不符合题目给定的移动规则。