#3010. 「JOI 2019 Final」勇者比太郎

内存限制:256 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: WAAutoMaton

题目描述

译自 JOI 2019 Final T1「勇者ビ太郎 / Bitaro the Brave

勇者比太郎正在面对恶魔。

为了攻击恶魔,比太郎会在一个 H×WH \times W 的网格上放置三种道具(分别记作 J,O,I)并施放咒语。网格上往下数第 ii 行(1iH1 \le i \le H),左往右数第 jj 列(1jW1\le j \le W)的格子坐标记为 (i,j)(i, j)

现在,比太郎在网格的每个格子中放置了三种道具中的一种,比太郎将施放一个咒语,其威力取决于三种道具的排列方式。具体的,威力大小等于满足以下条件的有序四元组 (i,j,k,l)(1i<kH,1j<lW)(i, j, k, l) (1 \le i < k \le H, 1 \le j < l \le W) 的数量。

条件:(i,j)(i, j) 位置的格子上的道具为 J(i,l)(i, l) 位置上的道具为 O(k,j)(k, j) 位置上的道具为 I

比太郎想知道他的咒语的威力是多少。

请写一个程序,根据三种道具在网格上的排列,计算出咒语的威力(即满足上述条件的四元组数量)。

输入格式

从标准输入中读取数据。

第一行包括两个整数 H,WH, W,表示网格的高度和宽度。

接下来 HH 行,第 ii 行给出一个 WW 位长的字符串 SiS_i,表示网格第 ii 行的道具。

输出格式

输出数据到标准输出中。

输出一行一个整数,表示比太郎的咒语的威力。

样例

样例输入 1
3 4
JOIJ
JIOO
IIII
样例输出 1
3
样例说明 1

在这个样例中,33 个四元组分别是 (1,1,3,2),(2,1,3,3),(2,1,3,4)(1, 1, 3, 2), (2, 1, 3, 3), (2, 1, 3, 4)

样例输入 2
4 4
JJOO
JJOO
IIJO
IIIJ
样例输出 2
17

数据范围与提示

Subtask # 分值 H,WH, W
1 20 H,W100H, W \le 100
2 30 H,W500H, W \le 500
3 50 H,W3000H, W \le 3000

对于所有输入数据,有 2H,W30002 \le H, W \le 3000