Codeforces Round #556 (Div. 2) - B. Tiling Challenge

問題概要

Problem - B - Codeforces

5つの正方形からなる十字型を
n * nからなる四角形内の空いている箇所に当てはめたとき
四角形の空きが全て埋まるとき、YES、埋まらないときはNOを出力せよ。

解法

上の段から、下に向かって十字型が埋まるか貪欲に見ればよい。
十字型である以上、最上位段、最下位段で左右連続して
空きがある際には、必ず空きができるのでNOを出力することになる。

また、一つの十字型を埋めると5個の空きが埋まるため
5の倍数ではないときは、空きがでるか、十字型を埋めることはできない。

提出コード

n = int(input())
e = []
empty = 0
for i in range(n):
    t = deque(list(input()))
    e.append(t)
    empty += t.count('.')
if empty % 5 != 0:
    print("NO")
else:
    for i in range(n):
        for j in range(n):
            if i + 2 >= n:
                continue
            if j - 1 < 0:
                continue
            if j + 1 >= n:
                continue
            if e[i][j] == '#':
                continue
            if e[i + 1][j] == '#':
                continue
            if e[i + 2][j] == '#':
                continue
            if e[i + 1][j - 1] == '#':
                continue
            if e[i + 1][j + 1] == '#':
                continue
            e[i][j] = '#'
            e[i + 1][j] = '#'
            e[i + 2][j] = '#'
            e[i + 1][j - 1] = '#'
            e[i + 1][j + 1] = '#'
            empty -= 5
    if empty == 0:
        print('YES')
    else:
        print('NO')