/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 400 点
問題文
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が書かれている。 - マスのうち、丁度 2 つが同じ行にある。
- マスのうち、丁度 2 つが同じ列にある。
但し、ふたつの三つ組は、丁度一方に含まれるマスが存在する場合のみ区別します。
制約
- N は 2 以上 2000 以下の整数
- S_i は長さ N の
oとxからなる文字列
入力
入力は以下の形式で標準入力から与えられる。
N S_1 S_2 \vdots S_N
出力
答えを整数として出力せよ。
入力例 1
3 ooo oxx xxo
出力例 1
4
以下の 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
Score : 400 points
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 anowritten in cell (i,j). - If the j-th character of S_i is
x, there is anxwritten 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
owritten 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
oandx.
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