[白俊]14502研究所

研究所

質問する

人体致命ウイルスを研究する研究所がウイルスを漏らした.幸いにもウイルスはまだ拡散していないので、ウイルスの拡散を防ぐために、研究所に壁を建てたいと思っています.
研究所の大きさはN×Mの矩形として表すことができ、矩形は1である.×1サイズの正方形に分割します.研究所は1つのスペース、1つの壁で構成され、壁は1つのスペースでいっぱいです.
一部の格子にはウイルスが存在し、このウイルスは上下左右に隣接する格子に伝播することができる.新しく立てた壁は3つあるので,3つ立てなければならない.
たとえば、研究所がある場合を見てみましょう.

2 0 0 0 1 1 0
0 0 1 0 1 2 0
0 1 1 0 1 0 0
0 1 0 0 0 0 0
0 0 0 0 0 1 1
0 1 0 0 0 0 0
0 1 0 0 0 0 0

このとき、0はスペース、1は壁、2はウイルスがいる場所です.壁を立てなければ、ウイルスはすべてのスペースに拡散することができます.
2行1列、1行2列、4行6列に壁を設けると、地図の形は以下のようになります.

2 1 0 0 1 1 0
1 0 1 0 1 2 0
0 1 1 0 1 0 0
0 1 0 0 0 1 0
0 0 0 0 0 1 1
0 1 0 0 0 0 0
0 1 0 0 0 0 0

ウイルスが拡散した様子は以下の通りです.

2 1 0 0 1 1 2
1 0 1 0 1 2 2
0 1 1 0 1 2 2
0 1 0 0 0 1 2
0 0 0 0 0 1 1
0 1 0 0 0 0 0
0 1 0 0 0 0 0

3つの壁を設置した後、ウイルスが拡散できない場所を安全区域と呼ぶ.上の地図では、安全区域の大きさは27です.
研究所地図が与えられたタイミングで得られる安全領域の大きさの最値を求めるプログラムを作成した.

入力

第1行は、地図の縦方向サイズNおよび横方向サイズMを与える.(3 ≤ N, M ≤ 8)
2行目からN行目に地図の形状を与える.0はスペース、1は壁、2はウイルスの位置です.2の個数は2以上、10以下の自然数である.
スペースの数は3つ以上です.

しゅつりょく

最初の行で取得できるセキュリティ領域の最大サイズを出力します.

コミットコード

import sys
from itertools import combinations
from collections import deque
from copy import deepcopy

input = sys.stdin.readline

n, m = map(int, input().split())
table = [list(map(int, input().split())) for _ in range(n)]

dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]

e = [] # empty
v = [] # virus
for i in range(n):
    for j in range(m):
        if table[i][j] == 2:
            v.append([i, j]) # 2는 virus로 v에 저장
        elif table[i][j] == 0:
            e.append([i, j]) # 0은 빈 공간으로 e에 저장

# 빈 곳 중 3개를 골라 조합으로 만든다.
e = list(combinations(e, 3))

# bfs
def bfs(ee):
    s = deepcopy(table)
    result = 0
    # 조합 대입하기
    for a, b in ee:
        s[a][b] = 1
    q = deque()
    for i in v:
        q.append(i)
  
    while q:
        _x, _y = q.popleft()
        for i in range(4):
            x = _x + dx[i]
            y = _y + dy[i]

            if x < 0 or y < 0 or x >= n or y >= m: continue
            # 벽과 이미 바이러스인 곳을 피함.
            if s[x][y] == 1 or s[x][y] == 2: continue
            s[x][y] = 2
            q.append([x, y])

    # 0인 곳 개수 확인
    for i in range(n):
        for j in range(m):
            if s[i][j] == 0:
                result += 1
    return result

# 세워질 수 있는 벽의 조합을 모두 대입해서 가장 적은 0의 개수 찾기
maximum = 0
for ee in e:
    maximum = max(maximum, bfs(ee))
print(maximum)

入力値が小さいので、立てられる壁の組み合わせを見つけて、bfsを回すといいのですが…!

私は上の図で研究所を除いてすべて解き終わって、他の人の解を見るまで、私は入力値が小さいことを知らないで、組み合わせて壁の数を求めることができます.