← 返回题目列表

AtCoder · abc440_g

G. 鬼屋

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

分数: 600 点

问题陈述

万圣节季节到了。作为勇气的考验,你即将挑战鬼屋。

有一个鬼屋 F 楼层,每个楼层由一个 H-行按 W- 列网格。让细胞 (k,i,j) 是位于 i从顶部开始的第行和 j- 代表楼层的网格左侧的第列 k.

细胞内容 (k,i,j) 由字符表示 S_{k,i,j} 如下:

  • If S_{k,i,j} 是一个数字 (0 - 9),细胞 (k,i,j) 是一个空单元格,其硬币数量等于该数字表示的个位数整数。
  • If S_{k,i,j} is #,细胞 (k,i,j) 是壁细胞。

您可以直接从空单元格移动 (k,i,j) 到另一个单元格 (k', i', j') 如果细胞 (k', i', j') 是一个空单元格,并且满足以下条件之一:

  • k' = k 和 |i' - i| + |j' - j| = 1 很满意。
  • (k', i', j') = (k+1, i, j) 很满意。
  • (k', i', j') = (k-1, i, j) 满意,并且 梯子 放置在单元格中 (k,i,j).

你不能移出网格。

你被给予 Q 问题;回答他们每个人。的 i第一个问题(1 \leq i \leq Q)如下:

  • 如果您恰好选择一个空单元格并在那里放置一个梯子,请找到您访问的单元格中的最大硬币总数,从单元格开始 (G_i, A_i, B_i),并重复移动。

每个问题都是独立的。也就是说,为一个问题放置的梯子不会影响其他问题。

约束

  • F,H,W 是整数。
  • 1 \leq F \leq 10
  • 1 \leq H,W \leq 500
  • S_{k,i,j} 是一个数字 (0, 1, 2, 3, 4, 5, 6, 7, 8, 9)或 #. (1 \leq k \leq F, 1 \leq i \leq H, 1 \leq j \leq W)
  • Q 是一个整数。
  • 1 \leq Q \leq 10^5
  • G_i, A_i, B_i 是整数。 (1 \leq i \leq Q)
  • 1 \leq G_i \leq F (1 \leq i \leq Q)
  • 1 \leq A_i \leq H (1 \leq i \leq Q)
  • 1 \leq B_i \leq W (1 \leq i \leq Q)
  • S_{G_i, A_i, B_i} 不是 #. (1 \leq i \leq Q)

输入

输入由标准输入按以下格式给出:

F H W
S_{1,1,1} S_{1,1,2} \cdots S_{1,1,W}
S_{1,2,1} S_{1,2,2} \cdots S_{1,2,W}
\vdots
S_{1,H,1} S_{1,H,2} \cdots S_{1,H,W}
S_{2,1,1} S_{2,1,2} \cdots S_{2,1,W}
S_{2,2,1} S_{2,2,2} \cdots S_{2,2,W}
\vdots
S_{2,H,1} S_{2,H,2} \cdots S_{2,H,W}
\vdots
S_{F,1,1} S_{F,1,2} \cdots S_{F,1,W}
S_{F,2,1} S_{F,2,2} \cdots S_{F,2,W}
\vdots
S_{F,H,1} S_{F,H,2} \cdots S_{F,H,W}
Q
G_1 A_1 B_1
G_2 A_2 B_2
\vdots
G_Q A_Q B_Q

输出

输出 Q 行。的 i- 第行 (1 \leq i \leq Q)应包含以下问题的答案 i- 第一个问题。


示例输入 1

3 5 6
######
##5###
#1#11#
#1#11#
######
######
##313#
#4##1#
#242##
######
######
#0####
##4###
###99#
######
3
1 2 3
2 3 2
3 2 2

示例输出 1

47
34
0

对于第一个问题,通过在单元格处放置梯子 (2,3,5) 并按如下方式移动,即可得出访问过的单元格中的硬币总数 47:

  1. 从单元格开始 (1,2,3) 在一楼。
  2. 上二楼,按顺序移动 (2,2,3) \to (2,2,4) \to (2,2,5) \to (2,3,5).
  3. 下到一楼,按顺序移动 (1,3,5) \to (1,4,5) \to (1,4,4) \to (1,3,4) \to (1,4,4).
  4. 上二楼,按顺序移动 (2,4,4) \to (2,4,3) \to (2,4,2) \to (2,3,2) \to (2,4,2) \to (2,4,3) \to (2,4,4).
  5. 上三楼,按顺序移动 (3,4,4) \to (3,4,5).

对于第二个问题,通过在单元格处放置梯子 (2,4,4) 并按如下方式移动,即可得出访问过的单元格中的硬币总数 34:

  1. 按顺序移动 (2,3,2) \to (2,4,2) \to (2,4,3) \to (2,4,4) 在二楼。
  2. 下到一楼,按顺序移动 (1,4,4) \to (1,4,5) \to (1,3,5) \to (1,3,4) \to (1,4,4).
  3. 上二楼并进入牢房 (2,4,4).
  4. 上三楼,按顺序移动 (3,4,4) \to (3,4,5).

第三题,无论你如何放置梯子,都无法从起始单元格移动 (3,2,2).


示例输入 2

3 6 30
31#990#7###71298#6#9####3##04#
###66###6######7#4#3#1079239#6
891###8#73#7#5838#589#225#1282
#####5#306#9#38#50##6#71##8658
6#68#4#5###30###3#5716987#####
06#8####3#####134#5##2##28#169
#5#11####0#75#8######28#6#904#
85#71####0##9#7#0##8#2##00####
#1#09#3772#838#67#6##261###0#4
#4##78###7#########9#9#488##08
43#1##4632##46714436##849#77#6
8#83#61##4#14476#9#1##72#3####
5#99####52##6#9####9#4#4132#3#
##910#27529#69##491###0#06#9##
0#60845#02##28##610#2####25#6#
#229156374##47#30907#60#####28
#0#810#54###21##1#3###8#5917##
###6#56#60##04#73###6255###2##
10
3 4 23
3 2 4
1 4 14
2 3 12
1 1 16
1 2 9
3 5 6
1 3 19
2 2 4
3 4 9

示例输出 2

136
217
474
255
474
285
217
451
251
217