Самый дешёвый шов
Фоторедактор сужает снимок, вырезая из него швы. Шов — по одному пикселю в каждой строке, сверху донизу, причём пиксели соседних строк стоят в одном столбце или в соседних. У каждого пикселя есть энергия — насколько он выделяется среди соседей, — а энергия шва равна сумме энергий его пикселей. Найдите шов с наименьшей энергией: его вырезание заметно меньше всего.
Если таких швов несколько, выведите любой. Третий и четвёртый тесты — энергии настоящих фотографий автора сайта шириной 120 пикселей.
Вход
В первой строке высота H и ширина W снимка (1 ≤ H, W; H·W ≤ 4·105). Дальше H строк по W целых чисел от 0 до 1530 — энергии пикселей.
Выход
В первой строке — энергия самого дешёвого шва. Во второй — H номеров столбцов этого шва сверху вниз, столбцы нумеруются с единицы.
Примеры
Пример 1
7 10 37 58 68 73 48 100 79 90 84 95 104 63 76 61 58 68 89 101 92 64 76 58 79 83 89 100 110 84 84 87 75 118 104 70 60 48 35 28 35 44 333 371 272 109 61 107 99 163 150 65 289 166 355 263 156 162 207 214 237 183 311 411 267 109 92 138 163 212 197 94
552 5 5 5 6 5 5 5
Пример 2
3 3 5 1 5 5 5 1 1 5 5
7 2 1 1
Ограничения
- Время · Python
- 5000 мс
- Время · Go
- 1000 мс
- Память
- 256 МБ
- Проверка
- 10 тестов
Разбор
Открывайте по ступеням: каждая следующая подсказывает больше. Можно сразу к решению — но задача, решённая с одной подсказкой, запоминается лучше.
1Подсказка 1
Простая идея: начать с самого дешёвого пикселя верхней строки и каждый раз шагать к самому дешёвому из трёх соседей снизу. Проверьте её на первом примере.
2Подсказка 2
Пусть для каждого пикселя предыдущей строки уже известна энергия самого дешёвого шва сверху до него. Как отсюда получить то же для пикселя текущей строки?
3Идея
M[y][x] — энергия самого дешёвого шва от верхней строки до пикселя (x, y). Такой шов приходит в (x, y) из одного из трёх пикселей над ним, и до того пикселя он сам самый дешёвый. Поэтому M[y][x] = E[y][x] + min(M[y−1][x−1], M[y−1][x], M[y−1][x+1]), а ответ — наименьшее число нижней строки. Это seam carving, вернее, один его шаг.
4Разбор
Таблицу заполняем строка за строкой. Сам шов восстанавливаем с конца: встаём в самую дешёвую клетку нижней строки и поднимаемся к тому из трёх соседей сверху, у кого M меньше, — именно из него пришёл лучший шов. Хранить нужно всю таблицу M: для пути назад нужны все строки.
Жадный шов в первом примере стартует с самого дешёвого пикселя, 37, уходит влево и внизу упирается в камыш на берегу: 999. Таблица находит шов почти прямо посередине: 552. Дешёвое начало ничего не говорит о продолжении — это и есть причина считать для каждого пикселя лучший путь до него, а не один путь.
В Python строку таблицы удобно считать целиком: сдвинуть предыдущую строку на клетку влево и вправо и взять поэлементный минимум трёх списков.
4+Решение
5Сложность
O(H·W) времени и памяти: каждую клетку считаем один раз из трёх соседей.
6Типичные ошибки
- Жадный шов. Не проходит первый пример.
- Выход за край. У крайних столбцов соседей сверху два, а не три.
- Шов, который прыгает. При восстановлении нужно выбирать только среди трёх соседей сверху, а не самую дешёвую клетку всей строки.