|
Волна
(Время: 1 сек. Память: 16 Мб Сложность: 42%)
Поле размером N×M клеток заполнено целыми числами. Требуется найти на поле клетку, из которой волна, запущенная не более чем на K итераций, покроет площадь с максимальной суммой расположенных на ней чисел.
Пример распространения волны для поля размером 5 x 4. Волна запущена из клетки (3,3) и была остановлена после трех итераций. Белые клетки – клетки, не покрытые волной, серые и черные – клетки, покрытые волной. Клетки, покрытые волной на последней итерации, отмечены серым цветом.
Входные данные
Первая строка входного файла INPUT.TXT содержит натуральные числа N, M и K (N, M ≤ 15, K ≤ N + M). Следующие N строк содержат по M чисел, каждое из которых не превосходит 104 по абсолютной величине.
Выходные данные
В выходной файл OUTPUT.TXT выведите четыре числа R, C, P и S, где R – номер строки, C – номер столбца, из которых следует запустить волну, P – количество итераций распространения волны, S – максимальная сумма чисел, покрытых волной. Если существует несколько вариантов ответа, вывести тот, в котором число P минимально. Если таких вариантов несколько, вывести вариант, в котором число R минимально, если и таких несколько, вывести вариант, в котором число С минимально.
Пример
№ | INPUT.TXT | OUTPUT.TXT |
1 | 5 4 3
1 2 3 4
1 6 7 8
9 10 11 12
0 0 0 0
2 0 0 1 | 3 3 3 66 |
Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!
| |