ドーナツ
(paizaランク A 相当)
問題にチャレンジして、ユーザー同士で解答を教え合ったり、コードを公開してみよう！
下記の問題をプログラミングしてみよう！
あなたはドーナツ屋 paiza の店員です. この店では, チョコが埋め込まれた四角のドーナツが名物となっています.
H x W cm^2 の生地があります. これは 1 cm^2 ごとに区画されており, H x W 個の区画を持っています.
また, それぞれの区間には既にいくつかのチョコが散りばめられています.
この 1 枚の生地から四角いドーナツの形を 1 つ切り出すことができます.
具体的には次の工程をおこないます.
1. 上から y 番目、 左から x 番目の区間を中心に一辺が B cm の正方形の切れ目を入れる。
2. 上から y 番目、 左から x 番目の区間を中心に一辺が S cm の正方形の切れ目を入れることでドーナツ状の切れ目を完成させる。（S < B であることが保証されています）
生地を成す H*W 個の各区画について、その区画に含まれるチョコの数と、作る N 個のドーナツについての情報が与えられるので、各ドーナツにチョコがいくつ含まれることになるかを求めてください。
なお、 N 枚の生地について、含まれるチョコの分布は全て同じであることがわかっています。
例として、入力例 1 では、生地は 3 × 3 cm^2 であり、次の通り区画されています。
また、入力の情報から、生地には次の通りチョコが乗っていることがわかります。
左から 2 番目、上から 2 番目の区画を中心とする 3 × 3 の正方形をくり抜くと、次の図の水色の部分になります。
また、そこからさらに左から 2 番目、上から 2 番目の区画を中心とする 1 × 1 の正方形をくり抜くと、次のようなドーナツができあがります。
このドーナツに乗っているチョコの数は 40 個であるので、答えとして 40 を出力してください。
- 入力される値
-
H W N
C[1][1] ... C[1][W]
...
C[H][1] ... C[H][W]
y_1 x_1 B_1 S_1
...
y_N x_N B_N S_N
・1 行目では、ドーナツの生地の縦の長さ H(cm) と横の長さ W(cm) と作るドーナツの数 N が与えられます。
・続く H 行では、生地の 1 cm^2 に含まれるチョコの数が左上から順に見た目の通りに半角スペース区切りで与えられます。
・続く N 行のうち、i 行目では、i 番目に作るドーナツの中心の生地の上からの距離 y_i (cm) と左からの距離 x_i (cm) とドーナツの外側の一辺の長さ B_i (cm) と 内側の一辺の長さ S_i (cm) が与えられます。
入力値最終行の末尾に改行が１つ入ります。
文字列は標準入力から渡されます。 標準入力からの値取得方法はこちらをご確認ください
- 期待する出力
ans_1
...
ans_N
・i 行目に i 個目のドーナツに含まれるチョコの数 ans_i を出力してください。
・また、出力の末尾には改行を入れてください。
- 条件
-
・3 ≦ H , W ≦ 1,000
・1 ≦ N ≦ 100,000
・0 ≦ C[i][j] < 10 (1 ≦ i ≦ H , 1 ≦ j ≦ W)
・1 ≦ y_i ≦ H (1 ≦ i ≦ N)
・1 ≦ x_i ≦ W (1 ≦ i ≦ N)
・0 ≦ S_i < B_i ≦ min(H,W) (1 ≦ i ≦ N)
・S_i , B_i は奇数
・くり抜けないようなドーナツの入力は与えられないことが保証されている
- 入力例1
-
3 3 1
1 2 3
4 5 6
7 8 9
2 2 3 1
- 出力例1
-
40
- 入力例2
-
5 5 4
7 8 9 8 5
4 2 6 2 1
2 5 3 9 1
1 3 3 2 3
2 3 2 6 6
3 4 3 1
2 3 3 1
2 4 3 1
3 3 5 3
- 出力例2
-
21
46
42
68
