Ruudukko

from string import ascii_uppercase
char = {ascii_uppercase[i]:i for i in range(26)}

n = int(input())

board = [[e for e in input()] for i in range(n)]

answer = ['*'] * (2*n-1)
answer[0] = board[0][0]
answer[2*n-2] = board[n-1][n-1]
current_queue = [[0,0]]
new_queue = []
minimal = 26

def check(i, j):
    global n
    global answer
    global board
    
    if i == n-1:
        for k in range(i+j+1, 2*n-1):
            answer[k] = board[i][k-i] #answer[k] = r[i][j+k-i-j]
        return True
    elif j == n-1:
        for k in range(i+j+1, 2*n-1):
            answer[k] = board[k-j][j] #answer[k] = r[i+k-i-j][j]
        return True
    return False

def fill_up(i, j, k):
    global n
    global char
    global board
    global minimal
    global current_queue
    global new_queue
    if k == 0 or current_queue[k-1][0] == current_queue[k][0] - 1:
        if j < n-1:
            if char[board[i][j+1]] < minimal:
                new_queue = [[i, j+1]]
                minimal = char[board[i][j+1]]
            elif char[board[i][j+1]] == minimal:
                new_queue += [[i, j+1]]

    if i < n-1:
        if char[board[i+1][j]] < minimal:
            new_queue = [[i+1, j]]
            minimal = char[board[i+1][j]]
        elif char[board[i+1][j]] == minimal:
            new_queue += [[i+1, j]]
            

if n > 1:
    for i in range(1, 2*n-2):
        length = len(current_queue)
    
        if length == 1:
            if check(current_queue[0][0], current_queue[0][1]):
                break

        for j in range(length):
            fill_up(current_queue[j][0], current_queue[j][1], j)
        answer[i] = board[new_queue[0][0]][new_queue[0][1]]
        current_queue = new_queue           
        new_queue = []
        minimal = 26


print(''.join(answer))

Test 1

Group: 1

Verdict: ACCEPTED

Test 2

Group: 1

Verdict: ACCEPTED

Test 3

Group: 1

Verdict: ACCEPTED

Test 4

Group: 1

Verdict: ACCEPTED

Test 5

Group: 1

Verdict: ACCEPTED

Test 6

Group: 2

Verdict: ACCEPTED

Test 7

Group: 2

Verdict: ACCEPTED

Test 8

Group: 2

Verdict: ACCEPTED

Test 9

Group: 2

Verdict: WRONG ANSWER

Test 10

Group: 2

Verdict: ACCEPTED

Test 11

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 12

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 13

Group: 3

Verdict: ACCEPTED

Test 14

Group: 3

Verdict: ACCEPTED

Test 15

Group: 3

Verdict: ACCEPTED