No.440 2次元チワワ問題

レベル : / 実行時間制限 : 1ケース 5.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 20
作問者 : 🍡yurahuna🍡yurahuna / テスター : btkbtk

0 ProblemId : 1095 / 出題時の順位表

問題文

$H$ 行 $W$ 列の方眼紙があります。
方眼紙の $i$ 行 $j$ 列目のマスを $(i, j)$ と書きます。左上のマスが $(1, 1)$ で、行の増える方向は下、列の増える方向は右です。
また、左上のマスが $(a, b)$, 右下のマスが $(c, d)$ であるような長方形領域を $\{(a, b), (c, d)\}$ と書くことにします。

方眼紙の各マスには 'c' または 'w' の文字が書かれています。
Cさんはこの方眼紙のある長方形領域にチワワが何匹含まれるかを知りたいです。
Cさんによれば、長方形領域 $R = \{(a, b), (c, d) \}$ に存在するチワワの数は、以下の条件を満たすマスの組 $((i_1, j_1), (i_2, j_2), (i_3, j_3))$ の数に等しいです。

  • $(i_1, j_1), (i_2, j_2), (i_3, j_3)$ はすべて長方形領域 $R$ 内部のマスである。すなわち、$a \leq i_1, i_2, i_3 \leq c$ かつ $b \leq j_1, j_2, j_3 \leq d$ である。
  • $(i_1, j_1), (i_2, j_2), (i_3, j_3)$ はどれも異なるマスで、上下左右いずれかの方向にこの順で並んでいる。ただしマスは隣接していなくともよい。すなわち以下のいずれかが成り立つ。
    • $i_1 = i_2 = i_3$ かつ $j_1 < j_2 < j_3$
    • $i_1 = i_2 = i_3$ かつ $j_1 > j_2 > j_3$
    • $i_1 < i_2 < i_3$ かつ $j_1 = j_2 = j_3$
    • $i_1 > i_2 > i_3$ かつ $j_1 = j_2 = j_3$
  • マス $(i_1, j_1)$ には文字 'c' が、マス $(i_2, j_2), (i_3, j_3)$ には文字 'w' が書かれている。
Cさんは $Q$ 個の長方形領域についてあなたに質問するので、それぞれの領域内に存在するチワワの数を教えてあげましょう。
ただし答えは32ビット型整数に収まるとは限らないことに注意してください。

入力

$H$ $W$
$s_1$
$s_2$
...
$s_H$
$Q$
$a_1$ $b_1$ $c_1$ $d_1$
$a_2$ $b_2$ $c_2$ $d_2$
...
$a_Q$ $b_Q$ $c_Q$ $d_Q$

  • 1行目には方眼紙の行数 $H$ , 列数 $W$ $(1 \leq H \leq 500, 1 \leq W \leq 500)$ がスペース区切りの整数で与えられる。
  • 2行目から $H + 1$ 行目には、方眼紙の各マスの情報が1行ごとに文字列で与えられる。
    • $i + 1$ 行目の 文字列 $s_i$ は $W$ 文字で構成され、$s_i$ の $j$ 文字目がマス $(i, j)$ に書かれている文字を表す。
    • $s_i$ には 'c', 'w' 以外の文字は含まれない。
  • $H + 2$ 行目には、質問の数 $Q$ $(1 \leq Q \leq 10000)$ が与えられる。
  • $H + 3$ 行目から $H + Q + 2$ 行目には、$i$ 番目の質問の情報 $a_i, b_i, c_i, d_i$ $(1 \leq i \leq Q, 1 \leq a_i, c_i \leq H, 1 \leq b_i, d_i \leq W, a_i \leq c_i, b_i \leq d_i)$ が与えられる。
    • $a_i, b_i, c_i, d_i$ は、$i$ 番目の質問で問われる長方形領域の左上のマスが $(a_i, b_i)$ , 右下のマスが $(c_i, d_i)$ であることを示す。

出力

出力は $Q$ 行からなる。
$i$ 行目には、$i$ 番目の質問に対する答えを1行で出力せよ。
ただし、答えは32ビット型整数に収まるとは限らないことに注意せよ。
また、末尾の改行を忘れないこと。

サンプル

サンプル1
入力
5 5
cwcww
wwwcw
wcwcw
ccwcc
wwwww
4
1 1 3 3
1 2 4 5
4 1 4 5
5 1 5 1
出力
3
11
0
0

1番目の質問で条件を満たす組は((1, 1), (2, 1), (3, 1)), ((2, 3), (2, 2), (2, 1)), ((3, 1), (3, 2), (3, 3))です。
2番目の質問で条件を満たす組は、例えば((3, 1), (3, 3), (3, 4)), ((4, 2), (2, 2), (1, 2)), ((3, 2), (3, 3), (3, 5))などがあります。

提出ページヘ