【AtCoder】【Python】ABC275 C問題

問題

ABC275 C

キーワード

組み合わせ全探索

コード

組み合わせ全探索でゴリ押し

10^9超えなければヨシ

import itertools
Grid = [input() for _ in range(9)]

# 9 x　9 = 81マスの正方形を考える
# 左上を固定して、他の3つの頂点を選ぶ
# 選んだ4つの頂点が正方形であるかどうかを判定する
# 頂点の組み合わせは81C4 = 1,663,740 ≒ 1.7 * 10^6
# なので十分間に合う

def is_square(coords_comb):
    '''頂点の組み合わせが正方形であるかどうかを判定する'''

    y1, x1 = coords_comb[0] # 左上
    y2, x2 = coords_comb[1] # 右上
    y3, x3 = coords_comb[2] # 左下
    y4, x4 = coords_comb[3] # 右下

    # 4つの頂点が正方形の頂点であるかどうかを判定
    if [Grid[y][x] for y, x in coords_comb] != ['#'] * 4:
        return False

    # 各辺の長さの2乗を計算
    # 辺
    d1 = (x1 - x2) ** 2 + (y1 - y2) ** 2
    d2 = (x1 - x3) ** 2 + (y1 - y3) ** 2
    d3 = (x3 - x4) ** 2 + (y3 - y4) ** 2
    d4 = (x2 - x4) ** 2 + (y2 - y4) ** 2
    # 対角
    d5 = (x1 - x4) ** 2 + (y1 - y4) ** 2
    d6 = (x2 - x3) ** 2 + (y2 - y3) ** 2

    # 正方形の条件
    # 1. 4辺の長さが等しい
    is_all_side_same = d1 == d2 == d3 == d4
    # 2. 対角線の長さが等しい
    is_all_diagonal_same = d5 == d6
    return is_all_side_same and is_all_diagonal_same

# 正方形の数のカウント
count = 0

# 9 x 9 = 81マスの頂点のリスト
coords = [ (y, x) for y in range(9) for x in range(9)]

# 頂点として4つの組み合わせを選ぶ（重複なし）
for coords_comb in itertools.combinations(coords, 4):
    # 頂点の組み合わせが正方形であるかどうかを判定
    if is_square(coords_comb):
        count += 1
print(count)