Problem : 81 - 行星調查

Problem Statistics

Solved Member: 36　　Submission: 86　　User Tried: 40

Statement:

在遙遠遙遠的宇宙中，日本航太總署終於發現了一顆可以供人類居住的行星，並將他命名為「JOI星」。星球的構造正如它的名字，是由「森林(Jungle)」、「海(Ocean)」以及「冰(Ice)」三種地形所組成的。透過簡單的調查，已經製成了一張簡略的地形圖。

地形圖是由南北長M km，以及東西寬N km的長方形所組成的。由北到南數過來第i行由東到西第j列以(i,j)來表示他的座標。每一個格子為長寬1 km的正方形，整張地圖就這樣被切成N*M個小塊，每一塊用J,O,I分別來標示「森林」、「海」、「冰」三種地形。

為了做移民到JOI星的準備，日本航太總署特別聘請了你，寫個程式來計算k個矩形中三種地形所佔的比率多寡。

Task:

給你調查完的地圖，請你寫個程式來計算三種地形的多寡。

Input:Output:

第1行有2個整數M, N，以空白區隔開來。代表火星的地圖為南北M km,東西N km的大小。
第2行有1個整數k，代表有多少的區域需要調查。
接下來的 M 行給出整個火星的地圖，以J,O,I三個字母表示，第 i+2 行的第 j 個字母代表座標(i,j)的地形。
接著 k 行每行有4個整數，Aj, Bj, Cj, Dj,代表調查區域的左上座標為(Aj,Bj)，右下角座標為(Cj,Dj)。

請你輸出 k 行數字，每1行有3個整數，分別代表每一筆尋問的矩形當中，森林、海、以及冰的數量。

Sample Input:Sample Output:

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

1 3 2
3 5 2
0 1 0
10 11 7

HINT:

1 ≤ M ≤ 1000 M為地圖南北向的長度
1 ≤ N ≤ 1000 N為地圖東西向的長度
1 ≤ K ≤ 100000 調查的數量

30%測資滿足：M ≤ 50 且 K ≤ 100
50%測資滿足：M ≤ 50

範例測資中，第二筆詢問的示意圖，上方為北方。

Source:

JOI 2010/2011 本選

Problem Setter

Nekosyndrome

Testdata:

Test	Time	Memory	Score
0	2000ms	65536kb
1	2000ms	65536kb	10
2	2000ms	65536kb	10
3	2000ms	65536kb	10
4	2000ms	65536kb	10
5	2000ms	65536kb	10
6	2000ms	65536kb	10
7	2000ms	65536kb	10
8	2000ms	65536kb	10
9	2000ms	65536kb	10
10	2000ms	65536kb	10