Ruudukko

n = int(input())
grid = [input() for _ in range(n)]
 
heads = [(0, 0)]
cur_seq = [ord(grid[0][0])]
 
for i in range(2*(n-1)):
    cur_seq += [999]
    new_heads = {}
    for (x, y) in heads:
        if x == n - 1:
            y += 1
        elif y == n - 1:
            x += 1
        else:
            if ord(grid[y + 1][x]) > ord(grid[y][x+1]):
                x += 1
            elif ord(grid[y + 1][x]) < ord(grid[y][x+1]):
                y += 1;
            else:
                c = ord(grid[y + 1][x])
                if c < cur_seq[-1]:
                    cur_seq[-1] = c
                    new_heads = {(x + 1, y), (x, y + 1)}
                elif c == cur_seq[-1]:
                    new_heads.add((x + 1, y))
                    new_heads.add((x, y + 1))
                continue
        c = ord(grid[y][x])
        if c < cur_seq[-1]:
            cur_seq[-1] = c
            new_heads = {(x, y)}
        elif c == cur_seq[-1]:
            new_heads.add((x, y))
    heads = new_heads
 
print("".join(chr(c) for c in cur_seq))

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

Test 12

Group: 3

Verdict: ACCEPTED

Test 13

Group: 3

Verdict: ACCEPTED

Test 14

Group: 3

Verdict: ACCEPTED

Test 15

Group: 3

Verdict: ACCEPTED