A18275. L形硬币
填空题
困难
知识点
题目描述
L形硬币
题目描述
有一个 n * n 的棋盘，某些格子里有硬币（用 o 表示），其余为空（用 x 表示）。
对于每一个有硬币的格子，我们可以选择同一行中的另一个硬币和同一列中的另一个硬币（均不同于当前格子），这三个格子组成一个“L”形（当前格子为拐角）。
请问一共有多少种不同的这样的三元组？
注意：不同的拐角格子视为不同的三元组；同一行或同一列中选择不同的另一个硬币也视为不同的三元组。
输入格式
第一行一个整数 n。
接下来 n 行，每行一个长度为 n 的字符串，由 o 和 x 组成。
输出格式
输出一个整数，表示满足条件的三元组总数。
输入样例 #1
2
oo
oo输出样例 #1
4输入样例 #2
3
ooo
oxx
xxo输出样例 #2
4说明提示
2≤n≤2000
参考答案
#include <iostream>
#include <string>
using namespace std;
const int MAXN = 2005;
int row[MAXN], col[MAXN];
string grid[MAXN];
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
for(int i = 0; i < n; ++i)
{
cin >> grid[i];
for(int j = 0; j < n; ++j)
{
if(grid[i][j] == 'o')
{
row[i]++;
col[j]++;
}
}
}
long long ans = 0; // 防止int溢出，2000*2000量级乘积会超int范围
for(int i = 0; i < n; ++i)
{
for(int j = 0; j < n; ++j)
{
if(grid[i][j] == 'o')
ans += 1LL * (row[i] - 1) * (col[j] - 1);
}
}
cout << ans << '\n';
return 0;
}
上一题
下一题