← 返回题目列表

AtCoder · joi2011ho1

A. 行星探索

中文机器翻译题面 查看原题

配点: 100 点

经过长途跋涉,载着你的超维移民船终于发现了一颗看似适合居住的星球。这颗星球被命名为 JOI Star,顾名思义,是“丛林”、“海洋”和“冰”的组合。 3 这是一颗严酷的星球,地形复杂。通过简单的勘察,绘制了规划住宅附近区域的地图。

规划住宅南北 M 公里,东西向 N 它的形状为 km 的矩形,1 它被分为平方公里的部分。所有部分都是 MN 从北方 p 行,从西边 q 栏目部分 由 (p, q) 代表。西北角部分 (1, 1) 东南角是 (M, N) 。每个部分的地形要么是“丛林”,“海洋”,要么是“冰”,“丛林”是 J,“海”是 O、“冰”是 I 字母字符 1 用字符表示。

现在,在制定详细的迁移计划时,K 我决定找出一个矩形区域内包含多少个“丛林”、“海洋”和“冰”部分。

課題

给定有关计划居住和要调查的区域的信息,编写一个程序来计算每个区域包含多少个“丛林”、“海洋”和“冰”部分。

制限

1 \leqq M \leqq 1\,000  规划居住南北长度(公里)
1 \leqq N \leqq 1\,000  规划居住区东西长度(公里)
1 \leqq K \leqq 100\,000  调查区域数量

入力

从标准输入读取以下数据。

  • 1 行是一个整数 书写 M, N ,以空格为分隔符,规划居住地为北向南。 M 公里,从东到西 N 代表公里大小。
  • 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) 分区数,“sea”(O) 隔室数量,“冰”(I) 表示分区数。 3 按此顺序写入整数,并用空格分隔。

採点基準

评分数据中,分配的分数 30 对于%,M \leqq 50 和 满足 K \leqq 100 满意。点分布 50 对于%,M \leqq 50 满意。


入力例 1

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

出力例 1

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

在此输入示例中, 第 2 区域就是上图所示的“丛林”。 3 部分,“海” 5 部分,“冰” 2 包含分区。