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$。

求满足以下所有条件的三个格子的三元组的数目：

这三个格子两两互不相同。 这三个格子中都写有 $o$。 恰有两个格子在同一行。 恰有两个格子在同一列。

这里，如果且仅如果某个格子恰好被其中一个三元组包含，则两个三元组被认为是不同的。

输入格式

输入从标准输入给出，格式如下： $N$ $S_1$ $S_2$ $\vdots$ $S_N$

输出格式

输出一个整数，表示答案。

3
ooo
oxx
xxo

4

4
oxxx
xoxx
xxox
xxxo

0

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

2960

提示

$N$ 是一个在 $2$ 到 $2000$（含）之间的整数。 $S_i$ 是一个由 $o$ 和 $x$ 组成的长度为 $N$ 的字符串。以下四个三元组满足条件：

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

标签: AtCoder|abc330D

来源

AtCoder|abc330D