洛谷 AT_abc275_c [ABC275C] Counting Squares 题解

大致题意

求以 # 为顶点的正方形个数。

思路分析

一道水黄。

首先我们可以看到题目范围非常小，仅仅只是一个 $9\times 9$ 的字符矩阵，而且还给了 $2$ 秒的时间，所以是完全可以暴力的。

可以用 set 存储每个 # 号的位置，枚举正方形的两个点 $i$ 和 $j$，设另外两个点为 $n$ 和 $m$，容易得到 $n_x=i_x+i_y-j_y,n_y=i_y-i_x+j_x$ 和 $m_x=j_x+i_y-j_y,m_y=j_y-i_x+j_x$ 四个公式求出 $n$ 和 $m$ 的坐标，在判断是否是 # 即可。

需要注意的是，由于每个角在枚举时都会算一遍，所以答案要乘 $\frac{1}{4}$。

Code

代码如下：

#include <iostream>
#include <set>
using namespace std;
signed main() {ios::sync_with_stdio(false), cin.tie(), cout.tie();char ch;int ans = 0;set <pair<int, int>> s;for (int i = 1; i <= 9; ++i)for (int j = 1; j <= 9; ++j) {cin >> ch;if (ch == '#') s.insert({i,j});//初始化 s}for (pair <int, int> i : s)for (pair <int, int> j : s)if (i != j) {//如果不是同一个点才进行操作int x = i.second - j.second, y = i.first - j.first;if (s.find({i.first + x, i.second - y}) != s.end() && s.find({j.first + x, j.second - y}) != s.end()) ++ans;//判断，累加答案}cout << ans / 4;//答案要除以 4return 0;
}