ABC 275 C - Counting Squares を全探索して息切れした

問題を一目見た時に、アプローチが分からず、
速攻でブラウザを閉じた(笑)

心を落ち着かせ、とりあえず、解説 をチラ見して、
"全探索" という単語を見かけたので、なるほどと思いトライしてみることにした。

思考のアプローチ
step1.四隅の角を、それぞれ for 文で動かしてみる
step2."step1"の組み合わせが正方形であることを判断する、if so, count up.
step3.重複を除いて count up を続け、最終値を output.

注意した点：
 計算量。四隅を導くだけでも、ざっくり O(8^8 = 16777216) 必要。
 判定 + 重複を除いたカウント処理を軽く すれば間に合いそう。
 っと見立てながらコーディング。

abc275c.cpp

#include <iostream>
#include <vector>
#include <cmath>
#include <string>
#include <map>
#include <algorithm>
using namespace std;

//(h1,w1)-----(h3,w3)
// 
// 
//(h2,w2)-----(h4,w4)

bool judge(int w1, int w2, int w3, int w4, int h1, int h2, int h3, int h4) {

	bool flag = true;

	int side1 = pow(w1 - w3, 2) + pow(h1 - h3, 2);
	int side2 = pow(w1 - w2, 2) + pow(h1 - h2, 2);
	int side3 = pow(w4 - w2, 2) + pow(h4 - h2, 2);
	int side4 = pow(w4 - w3, 2) + pow(h4 - h3, 2);

	int diagonal1 = pow(w4 - w1, 2) + pow(h4 - h1, 2);
	int diagonal2 = pow(w3 - w2, 2) + pow(h3 - h2, 2);

	if (diagonal1 != 2 * side3 || diagonal1 != 2 * side2 || side3 != side2) flag = false;
	if (diagonal2 != 2 * side4 || diagonal2 != 2 * side3 || side3 != side4) flag = false;
	if (side1 != side3 || side2 != side4 || side1 != side2 || side1 != side4 ) flag = false;

	return flag;
}

int main() {
	vector<string>S(9);
	for (int i = 0; i < 9; i++)
		cin >> S[i];
	map<string, int>memo;
	int cnt = 0;
	for (int w1 = 0; w1 < 8; w1++) {
		for (int w2 = 0; w2 < 8; w2++) {
			for (int w3 = w1+1; w3 < 9; w3++) {
				for (int w4 = w2+1; w4 < 9; w4++) {


					for (int h1 = 0; h1 < 8; h1++) {
						for (int h2 = h1+1; h2 < 9; h2++) {
							for (int h3 = 0; h3 < 8; h3++) {
								for (int h4 = h3+1; h4 < 9; h4++) {

									if(S[h1][w1] == '#' && S[h2][w2] == '#'&& S[h3][w3] == '#'&& S[h4][w4] == '#'){

										if (judge(w1, w2, w3, w4, h1, h2, h3, h4)) { 
											vector<pair<int, int>>num{ {w1,h1},{w2,h2},{w3,h3},{w4,h4} };
											sort(num.begin(), num.end());
											string key = "[" + to_string(num[0].first) + "," + to_string(num[0].second) + "]," + \
												         "[" + to_string(num[1].first) + "," + to_string(num[1].second) + "]," + \
												         "[" + to_string(num[2].first) + "," + to_string(num[2].second) + "]," + \
												         "[" + to_string(num[3].first) + "," + to_string(num[3].second) + "]";
											memo[key]++;
										}
									}

								}
							}
						}
					}



				}
			}
		}
	}
	cout << memo.size();
	//while (1) {}
	return 0;
}