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