青少年サメ

質問する

コード#コード#

'''
move는 물고기가 이동하는 함수
dfs로 상어가 갈 수 있는 모든 경우의 수를 탐색
'''

from pprint import pprint
from copy import deepcopy
d = [[-1, 0], [-1, -1], [0, -1], [1, -1], [1, 0], [1, 1], [0, 1], [-1, 1]]


def move(board, dit):
    for i in dit:
        y, x = dit[i]
        if y == -1 and x == -1:
            continue
        cnt = 0
        dy, dx = d[board[y][x][1]-1]
        ny = y+dy
        nx = x+dx
        while cnt < 8 and (ny < 0 or ny >= 4 or nx < 0 or nx >= 4 or board[ny][nx][0] == -1):
            cnt += 1
            dy, dx = d[(board[y][x][1]-1+cnt) % 8]
            ny = y+dy
            nx = x+dx
        board[y][x][1] += cnt
        board[y][x][1] %= 8
        if cnt == 8:
            continue

        if board[ny][nx][0] == 0:
            dit[board[y][x][0]] = [ny, nx]
            board[ny][nx] = board[y][x][::]
            board[y][x] = [0, 0]

        else:
            board[ny][nx], board[y][x] = board[y][x], board[ny][nx]
            dit[board[y][x][0]], dit[board[ny][nx][0]
                                     ] = dit[board[ny][nx][0]], dit[board[y][x][0]]


board = [[] for _ in range(4)]
dit = {}
for i in range(4):
    temp = list(map(int, input().split()))
    for j in range(0, 8, 2):
        board[i].append([temp[j], temp[j+1]])
        dit[temp[j]] = [i, j//2]

dit = dict(sorted(dit.items()))
dit[board[0][0][0]] = [-1, -1]
sum_v = board[0][0][0]
board[0][0][0] = -1

answer = 0


def dfs(y, x, sum_v, board, dit):
    global answer
    answer = max(answer, sum_v)
    temp = deepcopy(board)
    tempdit = deepcopy(dit)
    move(temp, tempdit)

    dy, dx = d[temp[y][x][1]-1]
    ny = y
    nx = x
    for i in range(4):
        ny += dy
        nx += dx
        if 0 <= ny < 4 and 0 <= nx < 4 and temp[ny][nx][0] > 0:
            value = temp[ny][nx][0]
            direction = temp[y][x][1]
            posy, posx = tempdit[value]

            temp[y][x] = [0, 0]
            temp[ny][nx][0] = -1
            tempdit[value] = [-1, -1]

            dfs(ny, nx, sum_v+value, temp, tempdit)
            temp[y][x] = [-1, direction]
            temp[ny][nx][0] = value
            tempdit[value] = [posy, posx]


dfs(0, 0, sum_v, board, dit)
print(answer)

に答える