import sys
input = sys.stdin.readline
from copy import deepcopy
dy = [-1,-1,0,1,1,1,0,-1]
dx = [0,-1,-1,-1,0,1,1,1]
def movefish(n,ocean):
y,x = where[n]
d = ocean[y][x][1]
for i in range(8):
y1,x1 = y+dy[(i+d)%8],x+dx[(i+d)%8]
if 4>y1>=0 and 4>x1>=0:
if ocean[y1][x1]:
if ocean[y1][x1][0] == -1:
continue
ocean[y][x] = ocean[y1][x1]
where[ocean[y][x][0]] = (y,x)
else:
ocean[y][x] = 0
ocean[y1][x1] = (n,(i+d)%8)
where[n] = (y1,x1)
break
def moveall(ocean):
ocean = deepcopy(ocean)
alive = {i:0 for i in range(1,17)}
for i in range(4):
for j in range(4):
if ocean[i][j]:
if ocean[i][j][0] != -1:
alive[ocean[i][j][0]] = 1
where[ocean[i][j][0]] = (i,j)
for n in range(1,17):
if alive[n]:
movefish(n,ocean)
return ocean
def DFS(ocean,result):
global maxresult
newocean = moveall(ocean)
sy,sx = where[-1]
sd = newocean[sy][sx][1]
newocean[sy][sx] = 0
sy += dy[sd]
sx += dx[sd]
while 4>sy>=0 and 4>sx>=0:
if newocean[sy][sx]:
n,d = newocean[sy][sx]
newocean[sy][sx] = (-1,d)
DFS(newocean,result+n)
newocean[sy][sx] = (n,d)
sy += dy[sd]
sx += dx[sd]
maxresult = max(maxresult,result)
ocean = [[0]*4 for i in range(4)]
for i in range(4):
data = [*map(int,input().split())]
for j in range(4):
ocean[i][j] = (data[j*2],data[j*2+1]-1)
result,d = ocean[0][0]
ocean[0][0] = (-1,d)
where = {}
maxresult = 0
DFS(ocean,result)
print(maxresult)
어마어마한 코드길이의 시뮬레이션 구현문제.
코드짜는데도 오래걸리고, 오타찾는데도 오래걸리고 힘들었다...
아이디어 자체는 매우 쉽다.
DFS + 백트래킹을 이용한 브루트포스로 모든 경우의 수를 고려하여 최대값을 구하면 된다.
코드짜는게 오래걸려서 그렇지;
그래도 나름 깔끔하게 잘 짠 것 같다. 오타만 아니었어도 ㅋㅋ;
오늘의 교훈) 오타내지 말자