AT_s8pc_5_e Broken Skateboard

编码员 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 \leq H \leq 777$ . - $1 \leq W \leq 777$ . - 具体单元的数量不超过 $7 \ 777$ 。 - 目标单元的数量正好是 $1$ 。