結果

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

ソースコード

diff #
raw source code

# TLE 解法: 候補マスのどれを良いマスにするかを 2^(候補数) 通り全探索(候補以外は全部植える)
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 nb(i, j):
        return [(i+a, j+b) for a, b in D if 0 <= i+a < N and 0 <= j+b < M]
    C = [(i, j) for i in range(N) for j in range(M)
         if S[i][j] == '.' and sum(S[x][y] == '#' for x, y in nb(i, j)) >= 2]
    best = 0
    for bits in range(1 << len(C)):
        G = {C[k] for k in range(len(C)) if bits >> k & 1}
        if len(G) <= best:
            continue
        if all(sum(S[x][y] == '.' and (x, y) not in G for x, y in nb(i, j)) >= 2 for i, j in G):
            best = len(G)
    return best
d = sys.stdin.read().split(); N, M = int(d[0]), int(d[1])
print(solve(N, M, d[2:2+N]))
0