Ruudukko

n = int(input())
# 'A' <= 'B'
 
letters = tuple(input() for i in range(n))
 
 
routes = [[0] * (n) for _ in range(n)]
# routes[0] = [array[0][:i + 1] for i in range(n)]
for i in range(1, n):
    routes[i][0] = 1
    for j in range(1, n):
        A = []
        B = []
        ups = 1  # b-a
        ai = i
        aj = j - 1
        bi = i - 1
        bj = j
        while ups:
            A.append(letters[ai][aj])
            B.append(letters[bi][bj])
            a = routes[ai][aj]  # vasen
            b = routes[bi][bj]  # ylös
            if a:
                ai -= 1
            else:
                aj -= 1
            if b:
                bi -= 1
            else:
                bj -= 1
            ups += b - a
        for k in range(len(B) - 1, -1, -1):
            if B[k] < A[k]:
                routes[i][j] = 1
                break
            if B[k] > A[k]:
                break
# print(routes)
A = []
ai = n - 1
aj = n - 1
while ai or aj:
    A.append(letters[ai][aj])
    a = routes[ai][aj]  # vasen
    if a:
        ai -= 1
    else:
        aj -= 1
A.append(letters[0][0])
print(''.join(reversed(A)))

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: ACCEPTED

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: TIME LIMIT EXCEEDED

Test 14

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 15

Group: 3

Verdict: TIME LIMIT EXCEEDED