AT_abc330_d [ABC330D] Counting Ls

题目描述

给定一个 $N \times N$ 的网格。我们用 $(i,j)$ 表示从上往下第 $i$ 行、从左往右第 $j$ 列的格子。
每个格子的状态由 $N$ 个长度为 $N$ 的字符串 $S_1,S_2,\dots,S_N$ 给出，具体如下：

• 当 $S_i$ 的第 $j$ 个字符为 o 时，$(i,j)$ 这个格子上写有 o。
• 当 $S_i$ 的第 $j$ 个字符为 x 时，$(i,j)$ 这个格子上写有 x。

请计算满足以下所有条件的格子三元组的个数：

• 这 $3$ 个格子互不相同。
• 这 $3$ 个格子上都写有 o。
• 这 $3$ 个格子中，恰好有 $2$ 个在同一行。
• 这 $3$ 个格子中，恰好有 $2$ 个在同一列。

注意，只有当两个三元组中存在仅属于其中一个三元组的格子时，这两个三元组才被认为是不同的。

输入格式

输入按以下格式从标准输入读入。

$N$
$S_1$
$S_2$
$\vdots$
$S_N$

输出格式

请输出满足条件的三元组的个数，结果为整数。

输入输出样例 #1

输入 #1

3
ooo
oxx
xxo

输出 #1

4

输入输出样例 #2

输入 #2

4
oxxx
xoxx
xxox
xxxo

输出 #2

0

输入输出样例 #3

输入 #3

15
xooxxooooxxxoox
oxxoxoxxxoxoxxo
oxxoxoxxxoxoxxx
ooooxooooxxoxxx
oxxoxoxxxoxoxxx
oxxoxoxxxoxoxxo
oxxoxooooxxxoox
xxxxxxxxxxxxxxx
xooxxxooxxxooox
oxxoxoxxoxoxxxo
xxxoxxxxoxoxxoo
xooxxxooxxoxoxo
xxxoxxxxoxooxxo
oxxoxoxxoxoxxxo
xooxxxooxxxooox

输出 #3

2960

说明/提示

限制条件

• $N$ 是 $2$ 到 $2000$ 之间的整数。
• $S_i$ 是仅由 o 和 x 组成的长度为 $N$ 的字符串。

样例解释 1

以下 $4$ 个三元组满足条件：

• $(1,1),(1,2),(2,1)$
• $(1,1),(1,3),(2,1)$
• $(1,1),(1,3),(3,3)$
• $(1,2),(1,3),(3,3)$

由 ChatGPT 4.1 翻译