← 返回题目列表

AtCoder · oidashi_a

A. 不完整的迷宫

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

問題文

你在路边发现了一个看起来可疑的迷宫生成器。 当你移动迷宫生成器时,垂直H方形,水平W它会自动生成一个正方形迷宫。 然而,它似乎出现了故障,生成了一个无法到达目标的迷宫。 所以你决定修改迷宫以便达到目标。

迷宫里有墙。#和道路.和起始方块S和目标广场G是1有正方形。 玩家从起始方格开始移动,并通过移动到四个垂直和水平方格中不是墙壁的相邻方格来瞄准目标方格。 您可以从此处选择墙方块。 仅1平方 我决定创建一个迷宫,您可以通过用路径替换方块来到达目标。

然而,如果你认为简单地将随机的墙变成路并不好玩,你可能会发现从起点到目标的最短路径长度是 我决定把墙变成一条路,这样 最長 。

请回答执行上述操作时从起点到目标的最短路径长度。


入力

H W
line_1
line_2
...
line_H
  • 第一行包含迷宫的高度。H和迷宫的宽度W (2 \leq H, W \leq 298)。
  • 从第二行开始H行包含W字符串 给出了line_i。每个line_i (1 \leq i \leq H)是 表示除以#,.,S,G它包括#是墙,.就是这样,S是起点,G代表目标点。

此外,S,G总是在迷宫里。1一一都有。

给定的迷宫是 如果您无法到达S不同编号的点最多为G,则可以通过用路径替换一堵墙来保证您能够到达目标。

出力

修改后的迷宫到目标的最短路径长度是 请输出1行。 在输出末尾添加换行符。


入力例1

6 8
S..#...#
##...#..
..###.##
........
.#######
.......G

出力例1

28

入力例2

5 6
#.S.#.
###...
...###
.#.#.G
.....#

出力例2

10

也可能存在循环路径。


入力例3

4 6
S.....
###.##
######
.....G

出力例3

8

厚墙也是可以的


入力例4

6 8
S.......
########
...#....
.##..##.
...#.#..
.#.G#..#

出力例4

12

从头开始S、G可能有一些道路未连接到其中任何一个。


入力例5

7 8
.#......
S#.#.###
...#.#.#
###.#.G.
.....#..
..##.#.#
........

出力例5

14