#P11788. [JOI 2019 Final] 勇者比太郎 / Bitaro the Brave

[JOI 2019 Final] 勇者比太郎 / Bitaro the Brave

题目描述

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

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

现在,比太郎在网格的每个格子中放置了三种道具中的一种,比太郎将施放一个咒语,其威力取决于三种道具的排列方式。具体的,威力大小等于满足以下条件的有序四元组 (i,j,k,l)(i,j,k,l),满足 (1i<kH,1j<lW)(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 行,每行 WW 个字符,描述网格每个格子的道具。

输出格式

一行一个整数,表示最大的威力。

3 4
JOIJ
JIOO
IIII
3
4 4
JJOO
JJOO
IIJO
IIIJ
17

提示

【数据范围与约定】

  • 2H3000 2 \le H \le 3000
  • 2W3000 2 \le W \le 3000
  1. 对于 20%20 \% 的数据,H100,W100 H \le 100,W \le 100
  2. 对于 30%30 \% 的数据,H500,W500 H \le 500,W \le 500
  3. 对于 50%50 \% 的数据,无特殊限制。