[BOJ 14502]研究所(Python)

9766 ワード
BFS コンポジット boj テキストリンク

質問する


研究所

問題の説明


これは表現力が必要な問題です.問題の要求は簡単だ.
  • 壁を3つ立てます.
  • ウイルスを伝播し、セキュリティ領域を確認します.
    • [3つの壁を立てる]を選択すると、リスト内のすべての壁が立てられる領域が配置され、それらを組み合わせて回転します.この3つの組み合わせが現れた場合、壁を立ててbfsを通じてウイルスを伝播し、領域全体を確認することができます.
    私はdeepcopyを使って図形をコピーし、壁を立ててウイルスを伝播しました.領域全体をチェックするのではなく、最初に0とカウントした後、ウイルスが伝播するたびに0の数を0に減らします.これにより、ウイルスを伝播し、領域全体を検査する必要がなくなります.

    プールコード

    from itertools import combinations
import copy

n, m = map(int, input().split())
graph = []
blank = []
virus = []
zerocnt = 0
answer = 0
for _ in range(n):
    graph.append(list(map(int, input().split())))

# 벽이 들어설 수 있는 좌표를 저장
for i in range(n):
    for j in range(m):
        if graph[i][j] == 0:
            zerocnt += 1
            blank.append((i, j))
        elif graph[i][j] == 2:
            virus.append((i, j))

# 바이러스를 퍼트린 후 안전 영역 검사
def check(arr, zerocnt):
    # zerocnt = 벽3개 박기전 0의 개수
    q = []
    dx = [-1, 0, 1, 0]
    dy = [0, 1, 0, -1]
    # 바이러스 퍼트리기
    # 바이러스를 퍼트리기만 하면 되는거라 que 필요 X
    q += virus
    while q:
        x, y = q.pop()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < n and 0 <= ny < m and arr[nx][ny] == 0:
                arr[nx][ny] = 2
                zerocnt -= 1
                q.append((nx, ny))
    return zerocnt - 3


for wall in combinations(blank, 3):
    arr = copy.deepcopy(graph)

    for x, y in wall:
        arr[x][y] = 1
    answer = max(answer, check(arr, zerocnt))
print(answer)
    ウィークリーダイジェスト31/2021
    Oracleブロック情報の表示