103303: [Atcoder]ABC330 D - Counting Ls

Problem Statement

You are given an $N \times N$ grid. Let $(i,j)$ denote the cell in the $i$-th row from the top and the $j$-th column from the left.
The states of the cells are given by $N$ strings of length $N$, $S_1, S_2, \dots, S_N$, in the following format:

• If the $j$-th character of $S_i$ is o, there is an o written in cell $(i,j)$.
• If the $j$-th character of $S_i$ is x, there is an x written in cell $(i,j)$.

Find the number of triples of cells that satisfy all of the following conditions:

• The three cells in the triple are distinct.
• All three cells have an o written in them.
• Exactly two of the cells are in the same row.
• Exactly two of the cells are in the same column.

Here, two triples are considered different if and only if some cell is contained in exactly one of the triples.

Constraints

• $N$ is an integer between $2$ and $2000$, inclusive.
• $S_i$ is a string of length $N$ consisting of o and x.

Input

The input is given from Standard Input in the following format:

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

Output

Print the answer as an integer.

Sample Input 1

3
ooo
oxx
xxo

Sample Output 1

4

The following four triples satisfy the conditions:

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

Sample Input 2

4
oxxx
xoxx
xxox
xxxo

Sample Output 2

0

Sample Input 3

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

Sample Output 3

2960

问题描述

给你一个 $N \times N$ 的网格。记 $(i,j)$ 为从上数第 $i$ 行，从左数第 $j$ 列的格子。

• 如果 $S_i$ 的第 $j$ 个字符为 o，则格子 $(i,j)$ 中写有 o。
• 如果 $S_i$ 的第 $j$ 个字符为 x，则格子 $(i,j)$ 中写有 x。

找出满足以下所有条件的格子三元组的数量：

• 三元组中的三个格子各不相同。
• 三个格子中均有 o 写在其中。
• 恰有两个格子在同一行。
• 恰有两个格子在同一列。

这里，只有当某个格子恰好在一个三元组中时，两个三元组才被认为是不同的。

约束条件

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

输入

输入通过标准输入给出以下格式：

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

输出

输出一个整数作为答案。

样例输入 1

3
ooo
oxx
xxo

样例输出 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)$

样例输入 2

4
oxxx
xoxx
xxox
xxxo

样例输出 2

0

样例输入 3

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

样例输出 3

2960