洛谷 AT_abc275_c [ABC275C] Counting Squares 题解
大致题意
求以 # 为顶点的正方形个数。
思路分析
一道水黄。
首先我们可以看到题目范围非常小，仅仅只是一个 9 × 9 9\times9 9×9 的字符矩阵，而且还给了 2 2 2 秒的时间，所以是完全可以暴力的。
可以用 set 存储每个 # 号的位置，枚举正方形的两个点
i
i
i 和
j
j
j，设另外两个点为
n
n
n 和
m
m
m，容易得到
n
x
=
i
x
+
i
y
−
j
y
,
n
y
=
i
y
−
i
x
+
j
x
n_x=i_x+i_y-j_y,n_y=i_y-i_x+j_x
nx=ix+iy−jy,ny=iy−ix+jx 和
m
x
=
j
x
+
i
y
−
j
y
,
m
y
=
j
y
−
i
x
+
j
x
m_x=j_x+i_y-j_y,m_y=j_y-i_x+j_x
mx=jx+iy−jy,my=jy−ix+jx 四个公式求出
n
n
n 和
m
m
m 的坐标，在判断是否是 # 即可。
需要注意的是，由于每个角在枚举时都会算一遍，所以答案要乘 1 4 \frac{1}{4} 41。
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;//答案要除以 4
return 0;
}