[Python] ABC018 C 30点

問題

C – 菱型カウント

回答

30点回答をスライドに従って求めます。

AtCoder Beginner Contest 018 解説 from AtCoder Inc.

R, C, K = map(int, input().split())
S = [input() for _ in range(R)]

# 黒マスの座標を保存
black_squares = []
for r in range(R):
    for c in range(C):
        if S[r][c] == 'x':
            black_squares.append((r, c))

ans = 0
# 中心 (r, c) を固定 
for r in range(K-1, R-K+1):
    for c in range(K-1, C-K+1):
        # 中心からマンハッタン距離がK未満の範囲で黒マスがある場合は不適。
        # 黒マスがない場合は答えに1加算。
        for r_black, c_black in black_squares:
            if abs(r_black - r) + abs(c_black - c) <= K -1:
                break
        else:
            ans += 1

print(ans)