結果
問題 | No.2675 KUMA |
ユーザー |
|
提出日時 | 2024-05-19 09:24:36 |
言語 | PyPy3 (7.3.15) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,238 bytes |
コンパイル時間 | 411 ms |
コンパイル使用メモリ | 82,720 KB |
実行使用メモリ | 199,964 KB |
最終ジャッジ日時 | 2024-12-20 16:45:11 |
合計ジャッジ時間 | 133,166 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | WA * 1 TLE * 1 |
other | WA * 6 TLE * 41 |
ソースコード
def get_observable_positions(x, y): directions = [ (2, -1), (2, 1), (-2, -1), (-2, 1), (-1, -2), (1, -2), (-1, 2), (1, 2) ] observable_positions = set() for dx, dy in directions: observable_positions.add((x + dx, y + dy)) return observable_positions # 入力の読み込み N = int(input().strip()) umas = [tuple(map(int, input().strip().split())) for _ in range(N)] uma_positions = set(umas) # すべての監視装置の配置場所を候補とする all_positions = set() for x, y in umas: all_positions.update(get_observable_positions(x, y)) # UMAの位置は監視装置を設置できないので除外する all_positions -= uma_positions # 監視装置のリスト all_positions = list(all_positions) # DFSによるバックトラッキング def dfs(covered, kma_count, index): global min_kma_count if kma_count >= min_kma_count: return if covered == uma_positions: min_kma_count = kma_count return for i in range(index, len(all_positions)): new_covered = covered | get_observable_positions(*all_positions[i]) dfs(new_covered, kma_count + 1, i + 1) min_kma_count = float('inf') dfs(set(), 0, 0) print(min_kma_count)