公式
C - Counting Squares 解説 by nok0
この問題は様々な解法が考えられますが、適当に実装すると同じ正方形を二回数えてしまうといった問題が起こることがあります。
ここでは実装方針の一例を紹介します。
まず、正方形を列挙する必要があります。これは、正方形の頂点のうち \(1\) 個を決めうち、次にその頂点を端点とする辺のうち片方を決め打つことで可能です。(なお、実装例では辺を反時計周りに向き付けし、決め打った頂点から次の頂点に向かう辺を探索しています。)
次に、正方形を重複して数えない方法を説明します。これには例えば std::set
を用いて、正方形を集合として管理すれば良いです。
また、std::set
が不要な方法もあります。先ほどの解法で何回同じ正方形を重複して数えているかを考えて、重複している回数で割ることによって答えを求めることができます。実装によって何回重複しているかは変化するので、気をつけてください。(実装例では、辺の向きを固定してるので同じ正方形をどの頂点を最初に選択したかで \(4\) 回カウントしています。)
実装例(c++):
#include <bits/stdc++.h>
using namespace std;
int main() {
vector<string> s(9);
for(auto &v : s) cin >> v;
auto valid = [&](int x, int y) {
return clamp(x, 0, 8) == x and clamp(y, 0, 8) == y and s[x][y] == '#';
};
set<set<pair<int, int>>> st;
for(int i = 0; i < 9; i++) {
for(int j = 0; j < 9; j++) {
for(int dx = -8; dx < 9; dx++) {
for(int dy = -8; dy < 9; dy++) {
if(!dx and !dy) continue;
int i2 = i + dx, j2 = j + dy;
int i3 = i2 - dy, j3 = j2 + dx;
int i4 = i3 - dx, j4 = j3 - dy;
if(valid(i, j) and valid(i2, j2) and valid(i3, j3) and valid(i4, j4)) {
set<pair<int, int>> sq;
sq.insert({i, j});
sq.insert({i2, j2});
sq.insert({i3, j3});
sq.insert({i4, j4});
st.insert(sq);
}
}
}
}
}
cout << st.size() << endl;
}
投稿日時:
最終更新: