Дана матрица A размером N*N, заполненная неотрицательными целыми числами. Расстояние между двумя элементами A
i j и A
p q определено как |i - p| + |j - q|.
Требуется заменить каждый нулевой элемент матрицы ближайшим ненулевым. Если есть две или больше ближайших ненулевых ячейки, нуль должен быть оставлен.
Ограничения: 1 <= N <= 200, 0 <= A
i j <= 1 000 000.
Входные данные
В первой строке содержится число N. Затем идут N строк по N чисел, разделённых пробелами и представляющих собой матрицу.
Выходные данные
Выводится N строк по N чисел, разделённых пробелами, - модифицированная матрица.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
1
0
|
0
|
|
2
|
3
5 0 0
0 0 0
0 0 6
|
5 5 0
5 0 6
0 6 6
|