from collections import deque
from copy import deepcopy
n, m, d = map(int, input().split())
from itertools import combinations
orig_graph = [list(map(int, input().split())) for _ in range(n)]
orig_enemies = deque()
for i in range(n):
for j in range(m):
if orig_graph[i][j] == 1:
orig_enemies.append([i, j])
answer = 0
def check(enemy):
y, x = enemy
return 0 <= y < n and 0 <= x < m and graph[y][x] == 1
def find_enemy(archer):
for dist in range(d):
for r in range(dist):
enemy_pos = [n - (r + 1), archer - (dist - r)]
if check(enemy_pos):
return enemy_pos
enemy_pos = [n - (dist + 1), archer]
if check(enemy_pos):
return enemy_pos
for r in range(dist - 1, -1, -1):
enemy_pos = [n - (r + 1), archer + (dist - r)]
if check(enemy_pos):
return enemy_pos
answer = 0
for archers in combinations(range(m), 3):
graph = deepcopy(orig_graph)
enemies = deepcopy(orig_enemies)
cnt = 0
while enemies:
catch = set()
catch_enemies = []
for archer in archers:
catch_enemy = find_enemy(archer)
if catch_enemy:
catch_enemies.append(catch_enemy)
for catch_enemy in catch_enemies:
y, x = catch_enemy
graph[y][x] = 0
catch.add((y * m + x))
temp_enemy = []
for enemy in enemies:
y, x = enemy
graph[y][x] = 0
if enemy not in catch_enemies and y + 1 < n:
temp_enemy.append([y + 1, enemy[1]])
for enemy in temp_enemy:
y, x = enemy
graph[y][x] = 1
enemies = temp_enemy
cnt += len(catch)
answer = max(answer, cnt)
print(answer)생각보다 까다로웠던 골드 4 구현 문제
궁수들을 배치하는 모든 경우의 수 mC3에 경우에 대해서 각각의 케이스에 대해 잡을 수 있는 적들의 수를 세면 되는 문제
N과 M이 15로 매우 작아서 시간복잡도는 그렇게 생각 안해도 되는 문제
for 궁수를 배치하는 경우의 수
while 각 턴이 끝날때 적들이 남지 않을 때까지
1. 각 궁수에 대해서 잡을 수 있는 적들의 좌표를 구한다
2. 구한 좌표에 대해서 중복값을 제거
3. 남아있는 적들을 옮긴다
4. 현재 경우에 수의 count 값을 중복을 제외한 적들의 숫자를 더해준다.
count 값을 최댓값을 갱신한다.
대략적인 알고리즘은 위와 같으며
디버깅하는데 너무 오래걸렸다
