Привет, codeforces! В рамках проекта по подготовке к олимпиадам по программированию в качестве задания была выдана эта задача на двумерное динамическое программирование.
Кратко суть задачи: дана матрица размера n2, где n ≤ 200 , в которой есть нулевые и ненулевые элементы. Расстояние на матрице между ячейками (x1, y1) и (x2, y2) определяется как dist = |x1 - x2| + |y1 - y2|. Каждый нулевой элемент нужно заменить ближайшим к нему ненулевым элементом, а если подходящих элементов несколько, то оставить без изменений.
Я написал решение на C++, которое получило вердикт Accepted, и решил ради эксперимента перенести его на python3, чтобы попрактиковаться с новым языком программирования. Вот что из этого вышло. Действий получается порядка O(n2), но с большой константой. При n = 200 должно пройти, но не проходит — вердикт TLE. Можно ли как-нибудь ускорить решение на python3, заменив ввод-вывод более быстрым (уже вроде как заменил, но может можно еще быстрее), или применив какие-нибудь другие хитрости, так, чтобы оно получило вердикт Accepted?
Кратко суть решения:
- Поиск ближайшего элемента для (x, y) среди всех элементов (x * , y * ) таких что, x ≥ x * и y ≥ y * .
- Поиск ближайшего элемента для (x, y) среди всех элементов (x * , y * ) таких что, x ≤ x * и y ≥ y * .
- Поиск ближайшего элемента для (x, y) среди всех элементов (x * , y * ) таких что, x ≥ x * и y ≤ y * .
- Поиск ближайшего элемента для (x, y) среди всех элементов (x * , y * ) таких что, x ≤ x * и y ≤ y * .
- Объединение ответов
Для каждого прохода 1-4 используем метод ДП, комбинируя ответы для соседних элементов, например, в 1 пункте: answer[x][y] = combine(answer[x - 1][y], answer[x][y - 1]) + 1
