最高分数:800 点
问题陈述
E869120 编码员正在考虑去一个尺寸为 H \times W。左上角的单元格是 (1,1),右下单元格是 (H,W).
溜冰场包括 1 球门单元、一些冰单元和一些混凝土单元。
溜冰场具有以下特点:
- 滑冰者在冰块上移动时会向同一方向移动。
- 当且仅当滑冰者停止时才能改变方向。
- 如果滑冰者进入球门,他/她就完成了比赛。然而,如果滑冰者走出滑冰场,他/她将无法再完成比赛。
而且,他的滑板坏了,所以移动速度会发生如下变化:
- 需要 k 秒移动一个单元格。最初, k is 1.
- 如果滑板出现在混凝土单元上, k 将增加 1.
- 他只能移动4个方向:上、下、左、右。
他想知道每个起始单元格完成游戏的最短时间。
请编写程序而不是E869120。
输入
输入由标准输入按以下格式给出:
H W
c_{1,1}c_{1,2}c_{1,3} ... c_{1,W}
c_{2,1}c_{2,2}c_{2,3} ... c_{2,W}
c_{3,1}c_{3,2}c_{3,3} ... c_{3,W}
...
c_{H,1}c_{H,2}c_{H,3} ... c_{H,W}
In 1-st线,滑冰链接的尺寸 H, W 。
来自 2-nd 行 H+1第行,给出了滑冰链接的状态。每个cell的状态表示如下:
.表示该单元是冰单元。#表示该单元是一个具体单元。G表示该单元格是目标单元格。
输出
打印 H 行采用以下格式:
d_{1,1} d_{1,2} d_{1,3} ... d_{1,W}
d_{2,1} d_{2,2} d_{2,3} ... d_{2,W}
d_{3,1} d_{3,2} d_{3,3} ... d_{3,W}
...
d_{H,1} d_{H,2} d_{H,3} ... d_{H,W}
d_{i,j} 表示从单元格开始的最短时间 (i,j)。 如果他无法从 (i,j)的值 d_{i,j} is -1.
约束
- 1 \leq H \leq 777.
- 1 \leq W \leq 777.
- 具体单元格数量不超过 7 \ 777.
- 目标单元格的数量恰好是 1.
子任务
子任务 1 [40 点]
- H = 1.
- W \leq 17.
子任务 2 [160 点]
- H \leq 17.
- W \leq 17.
- 具体单元格数量不超过 77.
子任务 3 [190 点]
- H \leq 177.
- W \leq 177.
- 具体单元格数量不超过 377.
子任务 4 [410 点]
- 没有其他限制。
示例输入 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, 4),需要 8 秒。
示例输入 2
1 8 #####G##
示例输出 2
15 10 6 3 1 0 1 3

上图为溜冰场。
如果他从 (1, 1),需要 8 秒。
示例输入 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