結果

問題 No.3813 Ashwreath
コンテスト
ユーザー sepa38
提出日時 2026-11-18 15:15:55
言語 PyPy3
(8.0.1 + ACL)
コンパイル:
pypy3 -mpy_compile _filename_
実行:
pypy3 _filename_
結果
WA  
実行時間 -
コード長 976 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 97 ms
コンパイル使用メモリ 64,148 KB
実行使用メモリ 57,124 KB
最終ジャッジ日時 2026-11-20 20:53:59
合計ジャッジ時間 3,126 ms
ジャッジサーバーID
(参考情報)
judge1_0 / judge2_0
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 2
other AC * 18 WA * 7
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code

# 誤解法: 候補マスを全部「良いマス」にしておき、条件を満たさないマスがある限り
#         そのマスに植物を植える(=良いマスから外す)ことを繰り返す貪欲
import sys
def solve(N, M, S):
    D = [(a, b) for a in (-1, 0, 1) for b in (-1, 0, 1) if (a, b) != (0, 0)]
    def cnt(i, j, pred):
        return sum(1 for a, b in D if 0 <= i+a < N and 0 <= j+b < M and pred(i+a, j+b))
    good = [[S[i][j] == '.' and cnt(i, j, lambda x, y: S[x][y] == '#') >= 2 for j in range(M)] for i in range(N)]
    plant = lambda x, y: S[x][y] == '.' and not good[x][y]
    changed = True
    while changed:
        changed = False
        for i in range(N):
            for j in range(M):
                if good[i][j] and cnt(i, j, plant) < 2:
                    good[i][j] = False
                    changed = True
    return sum(map(sum, good))
d = sys.stdin.read().split(); N, M = int(d[0]), int(d[1])
print(solve(N, M, d[2:2+N]))
0