← 返回题目列表

AtCoder · s8pc_5_e

E. 滑板坏了

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

最高分数: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