12100 - 2048(Easy)*

from copy import deepcopy

def maxNum(board):
    maxResult = 0
    for i in range(N):
        maxResult = max(maxResult, max(board[i]))
    return maxResult

def move2048(direction, board):
    #왼쪽
    if direction == 0:
        for i in range(N):
            pointer = 0
            for j in range(1, N):
                #왼쪽
                if board[i][j] != 0:
                    board[i][j] = 0
                    # [i, j] 앞이 0이라면 앞으로 당겨짐
                    if board[i][pointer] == 0:
                        board[i][pointer] = tmp
                    # [i, pointer] == [i, j] 이라면 더해서 앞으로 가고, pointer는 한칸 이동
                    elif board[i][pointer] == tmp:
                        board[i][pointer] *=2
                        pointer+=1
                    # 앞/뒤 모두 0이 아닌 경우
                    else:
                        pointer+=1
                        # board[i][j] = 0으로 초기화 시켰던거 다시 원상복구
                        board[i][pointer] = tmp
     #오른쪽
    elif direction == 1:
        for i in range(N):
            pointer = N-1
            # 뒤에서 첫 숫자는 제외 (N-2)
            for j in range(N-2, -1, -1):
                if board[i][j] != 0:
                    tmp = board[i][j]
                    board[i][j] = 0
                    if board[i][pointer] == 0:
                        board[i][pointer] = tmp
                    elif board[i][pointer] == tmp:
                        board[i][pointer] *= 2
                        pointer -= 1
                    else:
                        pointer -= 1
                        board[i][pointer] = tmp 
    #위쪽
    elif direction == 2:
        for j in range(N):
            pointer = 0
            for i in range(1, N):
                if board[i][j] != 0:
                    tmp = board[i][j] 
                    board[i][j] = 0
                    if board[pointer][j] == 0:
                        board[pointer][j] = tmp
                    elif board[pointer][j] == tmp:
                        board[pointer][j]  *= 2
                        pointer += 1
                    else:
                        pointer += 1
                        board[pointer][j] = tmp
                        
    elif direction == 3:
        for j in range(N):
            pointer = N-1
            for i in range(N-2, -1, -1):
                if board[i][j] != 0:
                    tmp = board[i][j]
                    board[i][j] = 0
                    if board[pointer][j] == 0:
                        board[pointer][j] = tmp
                    elif board[pointer][j] == tmp:
                        board[pointer][j] *= 2
                        pointer -= 1
                    else:
                        pointer -= 1
                        board[pointer][j] = tmp
                        
    return board

            
def dfs(board, count):
    global maxValue
    if count == 5:
        value = maxNum(board)
        maxValue = max(maxValue, value)
        return 
    # 우, 좌, 상, 하
    for i in range(4):
        # board를 꼭 deepcopy해서 함수를 거친 board 값이 다음 함수에 들어가지 못하도록 해야함
        dfs(move2048(i, deepcopy(board)), count+1)
        
        
N = int(input())
board = []
cnt = 0; maxValue = 0
for _ in range(N):
    i = list(map(int, input().split()))
    board.append(i)

dfs(board, cnt)
print(maxValue)