ひとつ三つ組の例をとって観察してみましょう。

......o
.......
.o....o

「マスのうち、丁度 \(2\) つが同じ行にある」「マスのうち、丁度 \(2\) つが同じ列にある」という条件から、このどちらにも当てはまるマスが丁度 \(1\) つあることが分かります。例の中では、右下の o がそれにあたります。

このマス \(s\) を決め打つ (全探索する) ことを考えましょう。残りの \(2\) マスはどのように選ぶことができるでしょうか?

結論としては、以下のような選び方をすることになります。

• \(s\) と同じ行にある \(s\) 以外の o マスを丁度 \(1\) つ選ぶ
• \(s\) と同じ列にある \(s\) 以外の o マスを丁度 \(1\) つ選ぶ

このような選び方の数は、 ( \(s\) と同じ行にある \(s\) 以外の o マスの個数 ) \(\times\) ( \(s\) と同じ列にある \(s\) 以外の o マスの個数 ) で求めることができます。

これは、あらかじめ各行各列の o マスの数を数えておくことで高速に求めることができます。

実装例 (C++):

#include<bits/stdc++.h>

using namespace std;

int main(){
  int n;
  cin >> n;
  vector<string> s(n);
  vector<long long> bi(n,0),bj(n,0);
  for(int i=0;i<n;i++){
    cin >> s[i];
    for(int j=0;j<n;j++){
      if(s[i][j]=='o'){
        bi[i]++;
        bj[j]++;
      }
    }
  }

  long long res=0;
  for(int i=0;i<n;i++){
    for(int j=0;j<n;j++){
      if(s[i][j]=='o'){
        res+=(bi[i]-1)*(bj[j]-1);
      }
    }
  }
  cout << res << "\n";
  return 0;
}