Задача 3. Lines 1 ≡

Входной файл:Стандартный вход   Ограничение времени:1 сек
Выходной файл:Стандартный выход   Ограничение памяти:256 Мб
Максимальный балл:100  

Условие

Поле для игры в Lines представляет собой квадрат размером 10 × 10 клеток. В каждой клетке может находиться шарик одного из шести цветов. Ход игрока состоит в перемещении одного из шариков на другую клетку. Разрешены только перемещения, которые можно сделать путём последовательности шагов на одну свободную клетку по горизонтали или вертикали.

После каждого хода все шарики, входящие в горизонтальные, вертикальные и диагональные ряды одноцветных шариков длиной 5 и более, удаляются с поля. Перед ходом на поле таких рядов нет.

Требуется по данному описанию поля найти такой ход, после которого с поля будет удалено максимальное количество шариков, и вывести это количество

Формат входных данных

Входной файл состоит из 10 строк по 10 символов в каждой. Символ "." (точка) обозначает пустую клетку, а символы с "1" по "6" — шарики различных цветов.

Формат выходных данных

Выходной файл должен содержать единственное целое число — максимальное количество удаляемых шариков.

Примеры тестов

№ Стандартный вход Стандартный выход
1 

........3.
....2..3..
....2.3...
....23....
..22.222..
.....2....
..55..2...
..25...2..
..2.....2.
..........

10

Разбор

Так как размеры поля 10x10 - небольшие, можно перебрать все варианты ходов и найти наилучший.

Чтобы это сделать - представим всё наше поле в виде графа. Сначала выбираем шарик, который будем двигать (полным перебором).

Для каждого шарика будем перебирать все возможные места, куда его можно передвинуть. Это делается путём запуска BFS из вершины выбранного шарика.

И для каждой перестановки считаем ответ.

0.059s 0.013s 13