18 жуткая

def find_max(start):
    global n, no_left, no_up, field_max
    answ = [[0 for i in range(n)] for j in range(n)]
    answ[start[0]][start[1]] = field_max[start[0]][start[1]]
    for i in range(start[0], n):
        for j in range(start[1], n):
            if (i, j) == start:
                continue
            if (i, j) in no_left:
                answ[i][j] = answ[i - 1][j] + field_max[i][j]
            elif (i, j) in no_up:
                answ[i][j] = answ[i][j - 1] + field_max[i][j]
            else:
                answ[i][j] = max(answ[i][j - 1], answ[i - 1][j]) + field_max[i][j]
    current = (n - 1, n - 1)
    while current != start:
        field_max[current[0]][current[1]] = 0
        if current in no_left:
            current = (current[0] - 1, current[1])
        elif current in no_up:
            current = (current[0], current[1] - 1)
        elif answ[current[0] - 1][current[1]] >= answ[current[0]][current[1] - 1]:
            current = (current[0] - 1, current[1])
        else:
            current = (current[0], current[1] - 1)
    field_max[start[0]][start[1]] = 0
    return answ[n - 1][n - 1]

def find_min(start):
    global n, no_left, no_up
    answ = [[0 for i in range(n)] for j in range(n)]
    answ[start[0]][start[1]] = field_min[start[0]][start[1]]
    for i in range(start[0], n):
        for j in range(start[1], n):
            if (i, j) == start:
                continue
            if (i, j) in no_left:
                answ[i][j] = answ[i - 1][j] + field_min[i][j]
            elif (i, j) in no_up:
                answ[i][j] = answ[i][j - 1] + field_min[i][j]
            else:
                answ[i][j] = min(answ[i][j - 1], answ[i - 1][j]) + field_min[i][j]
    current = (n - 1, n - 1)
    while current != start:
        field_min[current[0]][current[1]] = 10000000
        if current in no_left:
            current = (current[0] - 1, current[1])
        elif current in no_up:
            current = (current[0], current[1] - 1)
        elif answ[current[0] - 1][current[1]] <= answ[current[0]][current[1] - 1]:
            current = (current[0] - 1, current[1])
        else:
            current = (current[0], current[1] - 1)
    field_min[start[0]][start[1]] = 10000000
    return answ[n - 1][n - 1]


no_left_raw = [(0, (1, 19)), (1, (2, 12)), (2, (9, 12)), (3, (3, 4)), (5, (12, 16)), (6, (4, 7)), (7, (10, 16)), (10, (3, 4)), (10, (13, 17)), (11, (13, 16)), (13, (3, 9)), (16, (2, 4)), (16, (10, 18)), (18, (8, 16))]
no_up_raw = [(0, (1, 19)), (1, (2, 5)), (8, (3, 3)), (3, (7, 8)), (9, (8, 8)), (18, (9, 9)), (15, (12, 14)), (19, (14, 5)), (5, (16, 16)), (16, (17, 17))]
no_left = set()
for e in no_left_raw:
    for x in range(e[1][0], e[1][1] + 1):
        no_left.add((x, e[0]))
no_up = set()
for e in no_up_raw:
    for y in range(e[1][0], e[1][1] + 1):
        no_left.add((e[0], y))
start = [(0, 0), (1, 1), (2, 3), (2, 10), (2, 13), (3, 6), (8, 2), (9, 7), (11, 5), (12, 11)]
a = open('18.txt').readlines()
n = len(a)
for i in range(n):
    a[i] = list(map(int, a[i].split()))
answ_mx = 0
answ_mn = 100000000000
for st1 in start:
    for st2 in start:
        if st2 == st1:
            continue
        for st3 in start:
            if st3 in [st1, st2]:
                continue
            for st4 in start:
                if st4 in [st1, st2, st3]:
                    continue
                for st5 in start:
                    if st5 in [st1, st2, st3, st4]:
                        continue
                    field_max = [[0 for i in range(n)] for j in range(n)]
                    for i in range(n):
                        for j in range(n):
                            field_max[i][j] = a[i][j]
                    field_min = [[0 for i in range(n)] for j in range(n)]
                    for i in range(n):
                        for j in range(n):
                            field_min[i][j] = a[i][j]
                    cur_mx_answ = find_max(st1) + find_max(st2) + find_max(st3) + find_max(st4) + find_max(st5)
                    cur_mn_answ = find_min(st1) + find_min(st2) + find_min(st3) + find_min(st4) + find_min(st5)
                    answ_mx = max(answ_mx, cur_mx_answ)
                    answ_mn = min(answ_mn, cur_mn_answ)
print(answ_mn, answ_mx)