12100-2048

www.acmicpc.net/problem/12100

1. 매 시도마다 4 방향을 모두 DFS 로 재귀를 타줘야 한다.

2. 상, 하, 좌, 우 로 몰아주는 매열 수정을 구현한다.

3. 5번 수행하고 나면 매번 배열 중 가장 큰 값을 최댓값 업데이트 해준다.

n = int(input())
a = [list(map(int, input().split())) for _ in range(n)]

# 우, 좌, 상, 하
dx = [0, 0, -1, 1]
dy = [1, -1, 0, 0]

''''''
def dfs(time, a, dir):
    global max_ans, n
    if time >= 5:
        for i in range(n):
            max_ans = max(max_ans, max(a[i]))
        return

    na = [[0 for _ in range(n)] for _ in range(n)]
    # dir 에 따라 이동수행하여 a 기준으로 na 를 할당하자
    '''
    a 를 보고, dir 에 따라서 스택을 쌓아가자
    dir 이 상, 하 인 것과 좌, 우 인걸 두개로 구분해서 처리하자

    '''
    if dir == 0:
        for i in range(len(a)):
            stack = []
            rst = []
            for j in range(len(a)):
                if a[i][n - 1 - j]:
                    stack.append(a[i][n - 1 - j])
                # 두번째 부터는
                if len(stack) >= 2:
                    # 새로들어온게 같으면
                    if stack[-1] == stack[-2]:
                        # 같은거 2배해준거 따로 저장해주고
                        together = stack[-1] * 2
                        # 스택에서 뒤에 두개 빼주고
                        stack.pop()
                        stack.pop()
                        # 2배해준거 스택에 더해주고
                        stack.append(together)
                        # 몽땅 rst 에 추가
                        rst.extend(stack[:])
                        stack = []
            # 배치할 rst 를 완벽히 만들었당
            rst.extend(stack[:])
            loc = 0
            for v in rst:
                na[i][n - loc - 1] = v
                loc += 1

    elif dir == 1:
        for i in range(len(a)):
            stack = []
            rst = []
            for j in range(len(a)):
                if a[i][j]:
                    stack.append(a[i][j])
                # 두번째 부터는
                if len(stack) >= 2:
                    # 새로들어온게 같으면
                    if stack[-1] == stack[-2]:
                        # 같은거 2배해준거 따로 저장해주고
                        together = stack[-1] * 2
                        # 스택에서 뒤에 두개 빼주고
                        stack.pop()
                        stack.pop()
                        # 2배해준거 스택에 더해주고
                        stack.append(together)
                        # 몽땅 rst 에 추가
                        rst.extend(stack[:])
                        stack = []
            # 배치할 rst 를 완벽히 만들었당
            rst.extend(stack[:])
            loc = 0
            for v in rst:
                na[i][loc] = v
                loc += 1

    elif dir == 2:
        for i in range(len(a)):
            stack = []
            rst = []
            for j in range(len(a)):
                if a[j][i]:
                    stack.append(a[j][i])
                # 두번째 부터는
                if len(stack) >= 2:
                    # 새로들어온게 같으면
                    if stack[-1] == stack[-2]:
                        # 같은거 2배해준거 따로 저장해주고
                        together = stack[-1] * 2
                        # 스택에서 뒤에 두개 빼주고
                        stack.pop()
                        stack.pop()
                        # 2배해준거 스택에 더해주고
                        stack.append(together)
                        # 몽땅 rst 에 추가
                        rst.extend(stack[:])
                        stack = []
            # 배치할 rst 를 완벽히 만들었당
            rst.extend(stack[:])
            loc = 0
            for v in rst:
                na[loc][i] = v
                loc += 1

    elif dir == 3:
        for i in range(len(a)):
            stack = []
            rst = []
            for j in range(len(a)):
                if a[n - j - 1][i]:
                    stack.append(a[n - j - 1][i])
                # 두번째 부터는
                if len(stack) >= 2:
                    # 새로들어온게 같으면
                    if stack[-1] == stack[-2]:
                        # 같은거 2배해준거 따로 저장해주고
                        together = stack[-1] * 2
                        # 스택에서 뒤에 두개 빼주고
                        stack.pop()
                        stack.pop()
                        # 2배해준거 스택에 더해주고
                        stack.append(together)
                        # 몽땅 rst 에 추가
                        rst.extend(stack[:])
                        stack = []
            # 배치할 rst 를 완벽히 만들었당
            rst.extend(stack[:])
            loc = 0
            for v in rst:
                na[n - loc - 1][i] = v
                loc += 1

    time += 1
    for i in range(4):
        dfs(time, na, i)
''''''

time = 0
max_ans = 2
for i in range(4):
    dfs(time, a, i)

print(max_ans)