Камінці
Вам потрібно розподілити необмежену кількість каменів по клітинках ігрової дошки розміром n x n (де n знаходиться в діапазоні від 3 до 15). Кожна клітинка дошки містить певне додатне число від 10 до 99 включно. Наприклад, дошка розміром 6 x 6 може виглядати так:
Гравець розподіляє камені по дошці, дотримуючись таких умов:
У кожній клітинці може бути не більше одного каменя.
Жодні два камені не можуть бути розміщені в сусідніх клітинках. Дві клітинки вважаються сусідніми, якщо вони розташовані горизонтально, вертикально або навіть діагонально одна від одної. Дошка не є циклічною (не згорнута), тобто 44 і 61 в одному рядку не є сусідніми. Також не є сусідніми 33 і 75, 55 і 92.
Мета гри — максимізувати сумарну кількість балів у клітинках, зайнятих каменями.
Напишіть програму, яка послідовно зчитує дані з дошок і виводить максимальну кількість балів, яку можна отримати оптимальним розміщенням каменів.
Вхідні дані
Кожна дошка задається набором рядків. Кожен рядок містить серію чисел, розділених пробілами. Порожній рядок позначає кінець кожної дошки (включаючи останню).
Вихідні дані
Виведіть максимальну кількість балів, яку можна отримати, оптимально розподіливши камені на дошці, дотримуючись двох правил. Відповідь для кожного тесту слід виводити в окремому рядку.