分数: 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,2,3) 在一楼。
- 上二楼,按顺序移动 (2,2,3) \to (2,2,4) \to (2,2,5) \to (2,3,5).
- 下到一楼,按顺序移动 (1,3,5) \to (1,4,5) \to (1,4,4) \to (1,3,4) \to (1,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).
- 上三楼,按顺序移动 (3,4,4) \to (3,4,5).
对于第二个问题,通过在单元格处放置梯子 (2,4,4) 并按如下方式移动,即可得出访问过的单元格中的硬币总数 34:
- 按顺序移动 (2,3,2) \to (2,4,2) \to (2,4,3) \to (2,4,4) 在二楼。
- 下到一楼,按顺序移动 (1,4,4) \to (1,4,5) \to (1,3,5) \to (1,3,4) \to (1,4,4).
- 上二楼并进入牢房 (2,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