監視
14028 ワード
白駿
1. Python
import sys
import copy
dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]
direction = [[], [[0], [1], [2], [3]], [[0, 1], [2, 3]], [[0, 2], [2, 1], [1, 3], [3, 0]],
[[3, 0, 2], [1, 3, 0], [0, 2, 1], [2, 1, 3]], [[0, 1, 2, 3]]]
def watch(x, y, direction, tmp):
for d in direction:
nx = x
ny = y
while True:
nx += dx[d]
ny += dy[d]
if 0 <= nx < n and 0 <= ny < m and tmp[nx][ny] != 6:
if tmp[nx][ny] == 0:
tmp[nx][ny] = '#'
else:
break
def dfs(office, cnt):
global ans
tmp = copy.deepcopy(office)
if cnt == cctv_cnt:
c = 0
for i in tmp:
c += i.count(0)
ans = min(ans, c)
return
x, y, c = cctv[cnt]
for i in direction[c]:
watch(x, y, i, tmp)
dfs(tmp, cnt + 1)
tmp = copy.deepcopy(office)
n, m = map(int, input().split())
office = [list(map(int, input().split())) for _ in range(n)]
cctv_cnt = 0
cctv = []
ans = sys.maxsize
for i in range(n):
for j in range(m):
if office[i][j] != 0 and office[i][j] != 6:
cctv_cnt += 1
cctv.append([i, j, office[i][j]])
dfs(office, 0)
print(ans)
Reference
この問題について(監視), 我々は、より多くの情報をここで見つけました https://velog.io/@corone_hi/241.-감시テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol