import sys
input = sys.stdin.readline
from itertools import combinations
from collections import deque
dy = [1,-1,0,0]
dx = [0,0,1,-1]
def BFS():
flower = 0
while dq:
y,x,ylast,xlast,time,color = dq.popleft()
if visited[ylast][xlast] == 1: #전에 꽃이 폈으면
continue
if visited[y][x]:
if visited[y][x] == (time,-color):
visited[y][x] = 1
flower += 1
continue
visited[y][x] = (time,color)
for i in range(4):
y1,x1 = y+dy[i],x+dx[i]
if N>y1>=0 and M>x1>=0 and garden[y1][x1]:
dq.append((y1,x1,y,x,time+1,color))
return flower
N,M,G,R = map(int,input().split())
garden = []
for i in range(N):
garden.append([*map(int,input().split())])
spread = []
for i in range(N):
for j in range(M):
if garden[i][j] == 2:
spread.append((i,j))
result = 0
for GRlist in combinations(spread,G+R):
for Glist in combinations(GRlist,G):
visited = [[0]*M for i in range(N)]
dq = deque()
for y,x in Glist:
visited[y][x] = 1
dq.append((y,x,y,x,1,1)) #y,x,ylast,xlast,time,color
for y,x in GRlist:
if visited[y][x]:
continue
dq.append((y,x,y,x,1,-1))
visited = [[0]*M for i in range(N)]
result = max(result,BFS())
print(result)
시뮬레이션 구현문제 치고는(?) 약간 까다로울 순 있다.
그래도 구현은 구현이고 매우 쉽다.
일단 처음에 배양액을 어디에다 뿌릴지를 정해야한다. 나는 python의 combinations 함수를 이용해서 nCg+r 만큼 뽑고 그 중에서 g+rCg만큼 초록색, 나머지를 빨간색으로 하는 방법을 선택했다.
그리고 나서 BFS한 방식은
1. BFS에서 deque에 (현 위치, 이전 위치, 시간, 색깔)의 정보를 넣는다.
2. visited에는 (시간,색깔) 로 기록한다.
3. 만약 이전 위치에서 꽃이 폈다면, continue한다. (더 이상 배양액이 퍼지면 안되므로)
3. 현 위치가 visited라면, 시간은 같고 색깔은 다를 경우 꽃의 개수를 +1 해주고, 꽃으로 표시한다.
나쁘지 않은 문제였다.
오늘의 교훈) 구현은 쉽다.