eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Головоломка с каплями

Головоломка с каплями

Лимит времени 8 секунд
Лимит использования памяти 64 MiB

Браузерная игра-головоломка под названием "Bubble Puzzle" в настоящее время популярна в Интернет.

Игра ведется на доске 4×4, изначально в ее клетках находится несколько пузырей. Состояние каждого пузыря характеризуется натуральным числом, оно изменяется когда пузырь возбуждается. Возбудить пузырь можно кликнув по нем, после чего его состояние увеличивается на 1. Вы можете кликнуть и на пустой клетке. Тогда в этой клетке появится пузырь, состояние которого равно 1.

Когда пузырь достигает состояния 5 или выше, он взрывается и исчезает, а маленькие водяные капли начинают разлетаться в четырех направлениях (вверх, вниз, влево и вправо). Скорость движения этих капель равна одна клетка в секунду. В момент взрыва 4 капли находятся в той же клетке, где прежде был пузырь, через секунду они будут находиться в соседних клетках и так далее.

Летящая маленькая капля исчезает либо когда она врезается в пузырь, либо когда вылетает за границу доски. Когда капля ударяется в пузырь, его состояние увеличивается на 1. Аналогично, если в пузырь одновременно врезается несколько водяных капель, то его состояние увеличивается на их количество. Отметим, что капли в полете не сталкиваются друг с другом.

Как показано на рисунке, капли, полученные в результате взрыва, могут совершать другие взрывы. Другими словами, может возникнуть цепная пузырьковая реакция. Кликать (щёлкать) по клеткам запрещается, пока существует хотя бы одна летящая капля (то есть Вам следует ждать пока закончится процесс изменений состояний пузырей). В головоломке Вам следует взорвать все пузыри и очистить все клетки как можно быстрее.

В задаче следует вычислить наименьшее количество кликов, достаточных для выполнения задачи.

Входные данные

Входные данняе состоят из 4 строк, каждая из которых содержит 4 неотрицательных целых чисел, меньших 5. Каждое целое число описывает начальное состояние пузыря на клетке доски. 0 указывает на то, что клетка пустая.

Выходные данные

Вывести наименьшее количество кликов, достаточных для взрыва всех пузырей на доске. Если ответ больше 5, то следует вывести -1.

Пример

Входные данные #1
4 4 4 4
4 4 4 4
4 4 4 4
4 4 4 4
Выходные данные #1
1
Источник The 2011 35th Annual ACM Programming Contest Winter Camp