G - Haunted House 解説 /

実行時間制限: 3 sec / メモリ制限: 1024 MiB

配点 : 600 点

問題文

ハロウィンの季節がやってきました。あなたは肝試しとして、お化け屋敷に挑戦しようとしています。

F 階だてのお化け屋敷があり、各階は H 行 W 列のグリッドで表されます。k 階を表すグリッドの上から i 行目・左から j 列目のマスをマス (k,i,j) とします。

マス (k,i,j) の内容は文字 S_{k,i,j} によって、以下のように表されます。

  • S_{k,i,j} が数字 (0 - 9) の場合、マス (k,i,j) は空きマスであり、数字が表す 1 桁の整数と同じ枚数のコインがある。
  • S_{k,i,j} が # の場合、マス (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) は以下の通りです。

  • 好きな空きマスを 1 つだけ選んでハシゴを置いてから、マス (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

1 番目の質問において、マス (2,3,5) にハシゴを置いた状態で以下のように移動することで、訪れたマスにあるコインの合計枚数を 47 にすることができます。

  1. お化け屋敷の 1 階において、マス (1,2,3) から開始する。
  2. お化け屋敷の 2 階に上がり、マス (2,2,3) \to (2,2,4) \to (2,2,5) \to (2,3,5) の順に移動する。
  3. お化け屋敷の 1 階に降りて、マス (1,3,5) \to (1,4,5) \to (1,4,4) \to (1,3,4) \to (1,4,4) の順に移動する。
  4. お化け屋敷の 2 階に上がり、マス (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 階に上がり、マス (3,4,4) \to (3,4,5) の順に移動する。

2 番目の質問において、マス (2,4,4) にハシゴを置いた状態で以下のように移動することで、訪れたマスにあるコインの合計枚数を 34 にすることができます。

  1. お化け屋敷の 2 階において、マス (2,3,2) \to (2,4,2) \to (2,4,3) \to (2,4,4) の順に移動する。
  2. お化け屋敷の 1 階に降りて、マス (1,4,4) \to (1,4,5) \to (1,3,5) \to (1,3,4) \to (1,4,4) の順に移動する。
  3. お化け屋敷の 2 階に上がり、マス (2,4,4) にいる。
  4. お化け屋敷の 3 階に上がり、マス (3,4,4) \to (3,4,5) の順に移動する。

3 番目の質問において、どのようにハシゴを置いても開始地点のマス (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

Score : 600 points

Problem Statement

Halloween season has arrived. As a test of courage, you are about to challenge a haunted house.

There is a haunted house with F floors, and each floor is represented by an H-row by W-column grid. Let cell (k,i,j) be the cell at the i-th row from the top and j-th column from the left of the grid representing floor k.

The content of cell (k,i,j) is represented by the character S_{k,i,j} as follows:

  • If S_{k,i,j} is a digit (0 - 9), cell (k,i,j) is an empty cell with a number of coins equal to the single-digit integer represented by the digit.
  • If S_{k,i,j} is #, cell (k,i,j) is a wall cell.

You can move directly from an empty cell (k,i,j) to another cell (k', i', j') if cell (k', i', j') is an empty cell and one of the following is satisfied:

  • k' = k and |i' - i| + |j' - j| = 1 are satisfied.
  • (k', i', j') = (k+1, i, j) is satisfied.
  • (k', i', j') = (k-1, i, j) is satisfied, and a ladder is placed at cell (k,i,j).

You cannot move outside the grid.

You are given Q questions; answer each of them. The i-th question (1 \leq i \leq Q) is as follows:

  • Find the maximum total number of coins in the cells you visit if you choose exactly one empty cell and place a ladder there, start at cell (G_i, A_i, B_i), and repeatedly move.

Each question is independent. That is, a ladder placed for one question does not affect other questions.

Constraints

  • F,H,W are integers.
  • 1 \leq F \leq 10
  • 1 \leq H,W \leq 500
  • S_{k,i,j} is either a digit (0, 1, 2, 3, 4, 5, 6, 7, 8, 9) or #. (1 \leq k \leq F, 1 \leq i \leq H, 1 \leq j \leq W)
  • Q is an integer.
  • 1 \leq Q \leq 10^5
  • G_i, A_i, B_i are integers. (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} is not #. (1 \leq i \leq Q)

Input

The input is given from Standard Input in the following format:

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

Output

Output Q lines. The i-th line (1 \leq i \leq Q) should contain the answer to the i-th question.

Sample Input 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

Sample Output 1

47
34
0

For the first question, by placing a ladder at cell (2,3,5) and moving as follows, you can make the total number of coins in the visited cells 47:

  1. Start at cell (1,2,3) on the first floor.
  2. Go up to the second floor and move in the order (2,2,3) \to (2,2,4) \to (2,2,5) \to (2,3,5).
  3. Go down to the first floor and move in the order (1,3,5) \to (1,4,5) \to (1,4,4) \to (1,3,4) \to (1,4,4).
  4. Go up to the second floor and move in the order (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. Go up to the third floor and move in the order (3,4,4) \to (3,4,5).

For the second question, by placing a ladder at cell (2,4,4) and moving as follows, you can make the total number of coins in the visited cells 34:

  1. Move in the order (2,3,2) \to (2,4,2) \to (2,4,3) \to (2,4,4) on the second floor.
  2. Go down to the first floor and move in the order (1,4,4) \to (1,4,5) \to (1,3,5) \to (1,3,4) \to (1,4,4).
  3. Go up to the second floor and be at cell (2,4,4).
  4. Go up to the third floor and move in the order (3,4,4) \to (3,4,5).

For the third question, no matter how you place the ladder, you cannot move from the starting cell (3,2,2).

Sample Input 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

Sample Output 2

136
217
474
255
474
285
217
451
251
217