Codeforces Round #556 (Div. 2) - B. Tiling Challenge
問題概要
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')