prog.py

from copy import *
# Reading size of 2-dimension array:
n = int(input())

# Reading input array[n][n]:
arr = []
for i in range(n):
    arr.append([int(x) for x in input().split()])

for i in range(n):
    for j in range(n):
        print(arr[i][j], end = ' ')
    print()

# Struct Record:
class Record:

    def __init__(self, dist = 10**9, count = 2, row = -1, col = -1):
        self.dist, self.count, self.row, self.col = dist, count, row, col

    def inc(self):
        self.dist = self.dist + 1
        return self

# Combine two records:
def combine(a, b):
    if (a.dist < b.dist):
        return deepcopy(a)
    elif (a.dist > b.dist):
        return deepcopy(b)
    elif a.row == b.row and a.col == b.col:
        return deepcopy(a)
    else:
        return Record(a.dist, a.count + b.count, -1, -1)

# 2-D DP:
best_l_u = [[Record()] * n] * n
best_l_d = [[Record()] * n] * n
best_r_u = [[Record()] * n] * n
best_r_d = [[Record()] * n] * n

print('-' * 80)
for i in range(0, n):
    for j in range(0, n):
        if (arr[i][j] != 0): best_l_u[i][j] = deepcopy(Record(0, 1, i, j))
        elif i != 0 and j != 0: best_l_u[i][j] = combine(best_l_u[i-1][j], best_l_u[i][j-1]).inc()
        elif i == 0 and j != 0: best_l_u[i][j] = deepcopy(best_l_u[i][j-1]).inc()
        elif i != 0 and j == 0: best_l_u[i][j] = deepcopy(best_l_u[i-1][j]).inc()
        print('i = ', i, 'j = ', j, 'best_l_u = ', best_l_u[i][j].dist, best_l_u[i][j].count, best_l_u[i][j].row, best_l_u[i][j].col)

for i in range(n-1, -1, -1):
    for j in range(0, n):
        if (arr[i][j] != 0): best_l_d[i][j] = Record(0, 1, i, j)
        elif i != n-1 and j != 0: best_l_d[i][j] = combine(best_l_d[i+1][j], best_l_d[i][j-1]).inc()
        elif i == n-1 and j != 0: best_l_d[i][j] = deepcopy(best_l_d[i][j-1]).inc()
        elif i != n-1 and j == 0: best_l_d[i][j] = deepcopy(best_l_d[i+1][j]).inc()

for i in range(n-1, -1, -1):
    for j in range(n-1, -1, -1):
        if (arr[i][j] != 0): best_r_d[i][j] = Record(0, 1, i, j)
        elif i != n-1 and j != n-1: best_r_d[i][j] = combine(best_r_d[i+1][j], best_r_d[i][j+1]).inc()
        elif i == n-1 and j != n-1: best_r_d[i][j] = deepcopy(best_r_d[i][j+1]).inc()
        elif i != n-1 and j == n-1: best_r_d[i][j] = deepcopy(best_r_d[i+1][j]).inc()

for i in range(0, n):
    for j in range(n-1, -1, -1):
        if (arr[i][j] != 0): best_r_u[i][j] = Record(0, 1, i, j)
        elif i != 0 and j != n-1: best_r_u[i][j] = combine(best_r_u[i-1][j], best_r_u[i][j+1]).inc()
        elif i == 0 and j != n-1: best_r_u[i][j] = deepcopy(best_r_u[i][j+1]).inc()
        elif i != 0 and j == n-1: best_r_u[i][j] = deepcopy(best_r_u[i-1][j]).inc()

print('-' * 80)
for i in range(0, n):
    for j in range(0, n):
        print('i = ', i, 'j = ', j, 'best_l_u = ', best_l_u[i][j].dist, best_l_u[i][j].count, best_l_u[i][j].row, best_l_u[i][j].col)

for i in range(0, n):
    for j in range(0, n):
        if (arr[i][j] == 0):
            best = combine(combine(best_l_u[i][j], best_r_u[i][j]), combine(best_l_d[i][j], best_r_d[i][j]))
            #print('i = ', i, 'j = ', j, 'best = ', best.dist, best.count, best.row, best.col)
            #print(best.dist, best.count, best.row, best.col)
            if (best.count == 1):
                arr[i][j] = arr[best.row][best.col]
        print(arr[i][j], end=' ')
    print()