← 返回题目列表

AtCoder · joi2019ho_a

A. 勇敢的比特太郎(勇敢的比特太郎)

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

配点: 100 点

英雄比特太郎必须面对魔王。

Bitaro 是垂直的 H 行,横 W 你试图通过将珠宝、宝珠和金锭放置在该行的方格上并激活魔法来攻击魔王。下面,从网格顶部开始 i 行目 (1 \leqq i \leqq H),从左起 j 列目 (1 \leqq j \leqq W) 表示为 (i, j) 。

Bitaro 现在每个方块上都有这些。 3 类型 放置了 1 件。我们即将施展咒语,但该咒语的威力取决于网格上宝石、球体和金块的放置情况。具体来说,满足以下条件的整数 (i, j, k, l) (1 \leqq i < k \leqq H,1 \leqq j < l \leqq W)的对数就是魔法的威力。

条件:质量 (i, j) 有珠宝,质量 (i, l) 有一个球体, (k, j) 处有一块金块。

Bitaro对这个魔法的威力感到好奇。

给定网格上宝石、球体和金块的位置,创建一个程序来查找 Bitaro 激活的魔法的力量。


入力

输入是按以下格式从标准输入给出的。

H W
S_1
\vdots
S_H

S_i (1 \leqq i \leqq H) 是长度 字符串 W 。 j 文字目 (1 \leqq j \leqq W) 是 当 J 时,质量 (i, j) 有珠宝,O 时,质量 (i, j) 有一个球体, 表示金块放置在I 时,质量 (i, j) 。

出力

代表魔力的整数被发送到标准输出。 1 行。


制約

  • 2 \leqq H \leqq 3\,000.
  • 2 \leqq W \leqq 3\,000.
  • S_i 是长度 它是一个字符串 W (1 \leqq i \leqq H).
  • S_i 中的每个字符是 J,O,I (1 \leqq i \leqq H).

小課題

  1. (20 点) H \leqq 100,W \leqq 100.
  2. (30 点) H \leqq 500,W \leqq 500.
  3. (50 点)没有额外的限制。

入力例 1

3 4
JOIJ
JIOO
IIII

出力例 1

3

在此输入示例中,(i, j, k, l) = (1, 1, 3, 2), (2, 1, 3, 3), (2, 1, 3, 4) 的 3 对满足条件,所以答案是 3 。


入力例 2

4 4
JJOO
JJOO
IIJO
IIIJ

出力例 2

17