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

Камешки

Камешки

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

Вам следует распределить неограниченное количество камней по ячейкам n x n игровой доски (n находится в промежутке [3, 15]), каждая ячейка доски содержит некоторое положительное число от 10 до 99 включительно. Например доска размером 6 x 6 может выглядеть следующим образом:

prb1218

Игрок распределяет камешки по доске так, чтобы:

  • Не более одного камня находится в любой ячейке квадрата.

  • Никакие два вамня не находятся в соседних клетках. Две ячейки считаются соседними, если они являются горизонтальными, вертикальными или даже диагональными соседями. Доска не циклическая (не свернутая), то есть 44 и 61 в одной строке не являются соседними. Также соседними не являются 33 и 75, 55 и 92.

Цель игры состоит в том, чтобы максимизировать суммарное количество баллов в ячейках, занятых камнями.

Напишите программу, которая последовательно считывает данные с досок и выводит максимальное количество баллов, которое можно достичь оптимальным размещением камней.

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

Каждая доска задается набором строк. Каждая строка представляет собой разделенную пробелами серию чисел. Пустой строкой отмечен конец каждой доски (включая последнюю).

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

Выведите максимальное количество баллов, которое можно получить, оптимально распределяя камешки на доске при соблюдении двух правил. Ответ на каждый тест следует выводить в отдельной строке.

Пример

Входные данные #1
71 24 95 56 54
85 50 74 94 28
92 96 23 71 10
23 61 31 30 46
64 33 32 95 89

78 78 11 55 20 11
98 54 81 43 39 97
12 15 79 99 58 10
13 79 83 65 34 17
85 59 61 12 58 97
40 63 97 85 66 90
Выходные данные #1
572
683