Привет, codeforces! В рамках проекта по подготовке к олимпиадам по программированию в качестве задания была выдана эта задача на двумерное динамическое программирование.

Кратко суть задачи: дана матрица размера n², где n ≤ 200 , в которой есть нулевые и ненулевые элементы. Расстояние на матрице между ячейками (x₁, y₁) и (x₂, y₂) определяется как dist = |x₁ - x₂| + |y₁ - y₂|. Каждый нулевой элемент нужно заменить ближайшим к нему ненулевым элементом, а если подходящих элементов несколько, то оставить без изменений.

Я написал решение на C++, которое получило вердикт Accepted, и решил ради эксперимента перенести его на python3, чтобы попрактиковаться с новым языком программирования. Вот что из этого вышло. Действий получается порядка O(n²), но с большой константой. При n = 200 должно пройти, но не проходит — вердикт TLE. Можно ли как-нибудь ускорить решение на python3, заменив ввод-вывод более быстрым (уже вроде как заменил, но может можно еще быстрее), или применив какие-нибудь другие хитрости, так, чтобы оно получило вердикт Accepted?

Кратко суть решения:

1. Поиск ближайшего элемента для (x, y) среди всех элементов (x * , y * ) таких что, x ≥ x *  и y ≥ y * .
2. Поиск ближайшего элемента для (x, y) среди всех элементов (x * , y * ) таких что, x ≤ x *  и y ≥ y * .
3. Поиск ближайшего элемента для (x, y) среди всех элементов (x * , y * ) таких что, x ≥ x *  и y ≤ y * .
4. Поиск ближайшего элемента для (x, y) среди всех элементов (x * , y * ) таких что, x ≤ x *  и y ≤ y * .
5. Объединение ответов

Для каждого прохода 1-4 используем метод ДП, комбинируя ответы для соседних элементов, например, в 1 пункте: answer[x][y] = combine(answer[x - 1][y], answer[x][y - 1]) + 1