Official

C - Counting Squares Editorial by en_translator


There are many approaches to this problem, but a rough implementation may lead to an issue like counting the same square twice.

We introduce an example of implementation.

First, you need to enumerate squares. This can be done by first fixing one of the vertices of a square and then fixing one of the edges one of whose endpoint is the vertex. (Note that in the sample code we direct the edges counterclockwise and search the next edge from a fixed vertex to the next.)

Next, we need to avoid duplicates in counting. For example, we can manage squares in std::set to manage a square as a set.

There is an alternative approach that does not require std::set. We can consider how many time the same square is counted; we can obtain the answer by dividing by the count. Note that the count varies depending on implementation. (In the sample code, we count the same square four times each, depending on which vertex of the square was chosen first.)

Sample code (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;
}

posted:
last update: