← 返回题目列表

AtCoder · abc387_d

G. 蛇行

中文机器翻译题面 查看原题

分数: 400 点

问题陈述

给你一个网格 H 行和 W 列。 让 (i,j) 表示位于 i从顶部开始的第行和 j左起第 列。

每个单元格都是以下单元格之一:起始单元格、目标单元格、空单元格或障碍单元格。该信息由以下描述 H 字符串 S_1,S_2,\dots,S_H,每个长度 W。具体来说,细胞 (i,j) 是一个起始单元格,如果 j- 第一个字符 S_i is S,目标单元格,如果是 G,如果是空单元格 .,以及障碍物单元(如果是) #。保证只有一个起始单元和一个目标单元。

您当前位于起始单元格。 您的目标是通过重复移动到与您所在单元格相邻的单元格来到达目标单元格。 但是,您不能移动到障碍物单元上或移出网格,并且每次都必须在垂直移动和水平移动之间交替。 (第一次移动的方向可以任意选择。)

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

更正式地说,检查是否存在单元序列 (i_1,j_1),(i_2,j_2),\dots,(i_k,j_k) 满足以下所有条件。如果存在这样的序列,求最小值 k-1.

  • 对于每个 1 \leq l \leq k,它认为 1 \leq i_l \leq H 和 1 \leq j_l \leq W,和 (i_l,j_l) 不是障碍细胞。
  • (i_1,j_1) 是起始单元格。
  • (i_k,j_k) 是目标单元格。
  • 对于每个 1 \leq l \leq k-1, |i_l - i_{l+1}| + |j_l - j_{l+1}| = 1.
  • 对于每个 1 \leq l \leq k-2,如果 i_l \neq i_{l+1},那么 i_{l+1} = i_{l+2}.
  • 对于每个 1 \leq l \leq k-2,如果 j_l \neq j_{l+1},那么 j_{l+1} = j_{l+2}.

约束

  • 1 \leq H,W \leq 1000
  • H 和 W 是整数。
  • 每个 S_i 是一个长度为的字符串 W 组成 S, G, ., #.
  • 正好有一个起始单元格和正好一个目标单元格。

输入

输入由标准输入按以下格式给出:

H W
S_1
S_2
\vdots
S_H

输出

如果可以到达目标单元格,则打印最小移动数。否则,打印 -1.


示例输入 1

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

示例输出 1

7

如左图所示,可以移动为 (1,2)\rightarrow(2,2)\rightarrow(2,3)\rightarrow(3,3)\rightarrow(3,4)\rightarrow(2,4)\rightarrow(2,5)\rightarrow(1,5),到达目标单元格 7 移动。 这是不可能的 6 移动或更少,所以答案是 7.

请注意,您不能选择连续水平(或垂直)移动而不交替的路径,如右图所示。


示例输入 2

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

示例输出 2

-1

无法到达目标单元格。


示例输入 3

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

示例输出 3

148