A - 惑星探査 (Planetary Exploration)

Contest Duration: 2011-02-13(Sun) 01:00 - 2011-02-13(Sun) 05:00 (local time) (240 minutes) Back to Home

A - 惑星探査 (Planetary Exploration) Editorial

Time Limit: 500 msec / Memory Limit: 64 MB

配点： $100$ 点

あなたを乗せた超時空移民船は長旅の末，ついに居住可能と思われる惑星を発見した．JOI 星と名付けられたその惑星は，その名の通り「ジャングル (Jungle)」，「海 (Ocean)」，「氷 (Ice)」の $3$ 種類の地形が入り組んだ過酷な惑星である．簡単な調査により，居住予定地近辺の地図が作成された．

居住予定地は南北 $M$ km，東西 $N$ km の長方形の形をしており， $1$ km 四方の正方形の区画に分けられている．区画は全部で $MN$ 個あり，北から $p$ 行目，西から $q$ 列目の区画を $(p, q)$ で表す．北西の角の区画が $(1, 1)$ であり，南東の角の区画が $(M, N)$ である．各区画の地形は，「ジャングル」，「海」，「氷」のいずれかであり，「ジャングル」は J，「海」は O，「氷」は I の英字 $1$ 文字で表される.

さて，詳細な移住計画を立てるにあたり， $K$ 箇所の長方形領域内に「ジャングル」，「海」，「氷」がそれぞれ何区画含まれるかを調べることにした．

課題

居住予定地の情報と，調査対象となる領域の情報が与えられたとき，それぞれの領域について，「ジャングル」，「海」，「氷」が何区画含まれているかを求めるプログラムを作成せよ．

制限


$1 \leqq M \leqq 1\,000$	居住予定地の南北の長さ (km)
$1 \leqq N \leqq 1\,000$	居住予定地の東西の長さ (km)
$1 \leqq K \leqq 100\,000$	調査対象となる領域の個数

入力

標準入力から以下のデータを読み込め．

$1$ 行目には整数 $M, N$ が空白を区切りとして書かれており，居住予定地が南北に $M$ km，東西に $N$ km の広さであることを表す．
$2$ 行目には整数 $K$ が書かれており，調査対象となる領域の個数を表す．
続く $M$ 行には居住予定地の情報が書かれている． $i + 2$ 行目 ( $1 \leqq i \leqq M$ ) には，居住予定地の北から $i$ 行目に位置する $N$ 区画の情報を表す J，O，I からなる $N$ 文字の文字列が書かれている．
続く $K$ 行には調査対象となる領域が書かれている． $j + M + 2$ 行目 ( $1 \leqq j \leqq K$ ) には， $j$ 番目の領域を表す正整数 $a_j, b_j, c_j, d_j$ が空白を区切りとして書かれている． $(a_j, b_j)$ は調査領域の北西の角の区画を， $(c_j, d_j)$ は調査領域の南東の角の区画を表す．ただし， $a_j, b_j, c_j, d_j$ は， $1 \leqq a_j \leqq c_j \leqq M$ ， $1 \leqq b_j \leqq d_j \leqq N$ を満たす．

出力

標準出力に調査の結果を表す $K$ 行を出力せよ．出力の $j$ 行目には， $j$ 番目の調査領域に含まれる「ジャングル」(J) の区画数，「海」(O) の区画数，「氷」(I) の区画数を表す $3$ つの整数を，この順に空白を区切りとして書け．

採点基準

採点用データのうち，配点の $30$ %分については， $M \leqq 50$ かつ $K \leqq 100$ を満たす．配点の $50$ %分については， $M \leqq 50$ を満たす．

入力例 1Copy

Copy

4 7
4
JIOJOIJ
IOJOIJO
JOIJOOI
OOJJIJO
3 5 4 7
2 2 3 6
2 2 2 2
1 1 4 7

出力例 1Copy

Copy

この入力例では， $2$ 番目の領域は上図のように「ジャングル」を $3$ 区画，「海」を $5$ 区画，「氷」を $2$ 区画含む．

Source Name

JOI 2010/2011 本選問題1