DOJ Beginner Contest 12 C - Nature-Friendly Village
- サイト
- DOJ
- コンテスト
- DOJ Beginner Contest 12
- 問題
- C - Nature-Friendly Village
のグリッドの各マスは、家(#)か空き地(.)です。空き地に 1 本ずつ木を植えます。家ごとに周囲 8 マスに植えた木の本数を数え、その総和を 以上にしたいです。植える木の本数の最小値を求める問題です。できなければ を出力します(、全テストケースの の総和は 以下)。
総和を、木の側から数え直します。空き地 の周囲 8 マスにある家の個数を とすると、 に植えた木は、総和をちょうど だけ増やします。したがって総和は、木を植えた空き地の の和です。
この和を 以上にするには、 の大きい空き地から順に植えていくのが最善です。何本植えるにしても、同じ本数なら の大きいほうから選んだときに和が最大になるからです。すべての空き地に植えても に届かなければ、答えは です。
計算量はソートがいちばん重く、 です。
Python
from itertools import product
for _ in range(int(input())): R, C, K = map(int, input().split()) S = [input() for i in range(R)] l = [] for i, j in product(range(R), range(C)): if S[i][j] == "#": continue c = 0 for di, dj in product(range(-1, 2), repeat=2): if di == dj == 0: continue ni, nj = i + di, j + dj if ni not in range(R): continue if nj not in range(C): continue if S[ni][nj] == "#": c += 1 l.append(c) l.sort() s = 0 ans = 0 while l and s < K: s += l.pop() ans += 1 if s < K: print(-1) else: print(ans)l は空き地ごとの の列です。昇順にソートして末尾から pop することで、大きいほうから取り出しています。s が に届くか、空き地がなくなるまで植えます。 のときは 1 本も植えずに を出力します。