BOJ 14502研究所
25115 ワード
https://www.acmicpc.net/problem/14502
2秒、512 MBメモリ
input : N M (3 ≤ N, M ≤ 8) N行地図の形状(0スペース、1壁、2ウイルス位置) output : 安全区域最大出力 最初にitertoolsで解いた時は8*8が出てこなかったのでタイムアウトだと思って減らしてみました本当に本と他の人の答えが見つからない.
みんながfor文で壁を指定する方法を使っていて、そのスピードがちょっと速いと思ったので、問題を解いて、どうして7*7も吐けないのか...煩わしいので両方しました.
数が多い場合はitertoolsで解くと当然タイムアウトになりますが、小さい場合はこれの方が早いようです.
「For Moon」という言葉も覚えておきましょう
次はドアのために選択します.
2秒、512 MBメモリ
input :
みんながfor文で壁を指定する方法を使っていて、そのスピードがちょっと速いと思ったので、問題を解いて、どうして7*7も吐けないのか...煩わしいので両方しました.
数が多い場合はitertoolsで解くと当然タイムアウトになりますが、小さい場合はこれの方が早いようです.
「For Moon」という言葉も覚えておきましょう
import sys
from itertools import combinations
from _collections import deque
n, m = map(int, sys.stdin.readline().split())
data = []
temp = [[0] * m for _ in range(n)]
virus = []
empty = []
for i in range(n):
a = list(map(int, sys.stdin.readline().split()))
for j in range(m):
if a[j] == 2:
virus.append((i, j))
if a[j] == 0:
empty.append((i, j))
data.append(a)
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
ret = 0
def viruses():
q = deque()
for item in virus:
q.append(item)
while q:
x, y = q.popleft()
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
if nx >= n or nx < 0 or ny >= m or ny < 0:
continue
if temp[nx][ny] == 0:
temp[nx][ny] = 2
q.append((nx, ny))
def zeros():
cnt = 0
for i in range(n):
for j in range(m):
if temp[i][j] == 0:
cnt += 1
return cnt
for positions in combinations(empty, 3):
for i in range(n):
for j in range(m):
temp[i][j] = data[i][j]
for now_x, now_y in positions:
temp[now_x][now_y] = 1
viruses()
ret = max(ret, zeros())
print(ret)
-----------------------------------------------------------
import sys
n, m = map(int, sys.stdin.readline().split())
data = []
temp = [[0] * m for _ in range(n)]
for _ in range(n):
data.append(list(map(int, sys.stdin.readline().split())))
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
ret = 0
def virus(x, y):
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
if nx >= n or nx < 0 or ny >= m or ny < 0:
continue
if temp[nx][ny] == 0:
temp[nx][ny] = 2
virus(nx, ny)
def zeros():
cnt = 0
for i in range(n):
for j in range(m):
if temp[i][j] == 0:
cnt += 1
return cnt
def wall(count):
global ret
if count == 3:
for i in range(n):
for j in range(m):
temp[i][j] = data[i][j]
for i in range(n):
for j in range(m):
if temp[i][j] == 2:
virus(i, j)
ret = max(ret, zeros())
return
for i in range(n):
for j in range(m):
if data[i][j] == 0:
data[i][j] = 1
count += 1
wall(count)
data[i][j] = 0
count -= 1
wall(0)
print(ret)
以上の場合はいずれも組合せである.次はドアのために選択します.
Reference
この問題について(BOJ 14502研究所), 我々は、より多くの情報をここで見つけました https://velog.io/@jsin2475/BOJ-14502-연구소テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol