AT_s8pc_5_e.Broken Skateboard

普及+/提高

通过率：0%

AC君温馨提醒

该题目为【atcoder】题库的题目，您提交的代码将被提交至atcoder进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

编码员 E869120 正在考虑去溜冰场，溜冰场的大小为 $H \times W$ 。左上角单元格为 $(1,1)$ ，右下角单元格为 $(H,W)$ 。
溜冰场由 $1$ 个球门单元格、一些冰单元格和一些混凝土单元格组成。

溜冰场的特征如下：

滑冰者在冰格上移动时方向一致。
滑冰者只有在停止时才能改变方向。
如果滑冰者滑到了球门单元，他/她就完成了比赛。但是，如果滑冰者来到滑冰场外，则无法完成游戏。

此外，他的滑板坏了，因此移动速度会发生如下变化：

移动一个格子需要 $k$ 秒。最初， $k$ 为 $1$ 。
如果滑板滑到水泥格上， $k$ 将增加 $1$ 。
他只能向 4 个方向移动：上、下、左、右。

他想知道每个起始格完成游戏所需的最短时间。
请写出代替 E869120 的程序。

输入格式

在 $1$ 行中，给出了滑行链路 $H$ $W$ 的大小。
从 $2$ 行到 $H+1$ 行，给出了滑行链路的状态。每个单元格的状态表示如下：

. 表示该单元是冰单元。
# 表示该单元格为混凝土单元格。
G 表示该单元是目标单元。

输出格式

$d_{i,j}$ 表示从 $(i,j)$ 单元格开始计算的最短时间。如果他无法从 $(i,j)$ 单元格到达目标单元格，则 $d_{i,j}$ 的值为 $-1$ 。

输入输出样例

输入#1

6 6
......
.#....
......
......
......
...#.G

输出#1

-1 -1 -1 9 -1 5
-1 -1 -1 8 -1 4
-1 -1 -1 7 -1 3
-1 -1 -1 6 -1 2
-1 -1 -1 5 -1 1
7 6 5 2 1 0

输入#2
```
1 8
#####G##
```
输出#2
```
15 10 6 3 1 0 1 3
```

输入#3

9 9
....#..#.
#........
....#....
.#......#
...###...
##....#.#
....#...#
#....#...
.#.#..#.G

输出#3

54 37 52 29 38 38 17 53 18
43 36 60 28 37 37 16 65 17
40 35 38 27 26 36 15 39 16
35 22 21 20 19 18 14 16 10
28 27 26 16 16 25 13 36 9
28 17 16 15 14 13 7 9 5
18 17 16 14 8 7 6 5 2
41 22 52 13 15 37 5 51 1
22 14 13 7 6 5 2 1 0

说明/提示

$1 \leq H \leq 777$ .
$1 \leq W \leq 777$ .
具体单元的数量不超过 $7 \ 777$ 。
目标单元的数量正好是 $1$ 。

输入解题思路，AI测评打分。不知道怎么写?

首页