Камешки
Вам следует распределить неограниченное количество камней по ячейкам n x n игровой доски (n находится в промежутке [3, 15]), каждая ячейка доски содержит некоторое положительное число от 10 до 99 включительно. Например доска размером 6 x 6 может выглядеть следующим образом:
Игрок распределяет камешки по доске так, чтобы:
Не более одного камня находится в любой ячейке квадрата.
Никакие два вамня не находятся в соседних клетках. Две ячейки считаются соседними, если они являются горизонтальными, вертикальными или даже диагональными соседями. Доска не циклическая (не свернутая), то есть 44 и 61 в одной строке не являются соседними. Также соседними не являются 33 и 75, 55 и 92.
Цель игры состоит в том, чтобы максимизировать суммарное количество баллов в ячейках, занятых камнями.
Напишите программу, которая последовательно считывает данные с досок и выводит максимальное количество баллов, которое можно достичь оптимальным размещением камней.
Входные данные
Каждая доска задается набором строк. Каждая строка представляет собой разделенную пробелами серию чисел. Пустой строкой отмечен конец каждой доски (включая последнюю).
Выходные данные
Выведите максимальное количество баллов, которое можно получить, оптимально распределяя камешки на доске при соблюдении двух правил. Ответ на каждый тест следует выводить в отдельной строке.