Score : $400$ points

问题描述

给定一个 $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 写在其中。
• 正好有两个单元格在同一行。
• 正好有两个单元格在同一列。

这里，两个三元组被认为是不同的，当且仅当恰好有一个单元格只被其中一个三元组包含。

以上为通义千问 qwen-max 翻译，仅供参考。

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

update @ 2024/3/10 01:14:00