K. Крестики-нолики

Пете и Васе стало очень скучно на уроке биологии, и они решили поиграть в любимую всеми школьниками игру в крестики-нолики до пяти в ряд на бесконечном поле.

Рассмотрим кратко правила игры. Игра происходит на бесконечном клетчатом поле, два игрока делают ходы по очереди, первый игрок ходит крестиками, а второй – ноликами. В свой ход игрок выбирает свободную клетку поля и ставит туда свой символ. Если после хода очередного игрока на поле есть пять его символов подряд по вертикали, горизонтали или диагонали, то сделавший такой ход игрок объявляется победителем и игра заканчивается.

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

• этот ход приводит к немедленной победе Пети;
• не существует хода, который приводит к немедленной победе Пети, но если Петя сделает этот ход, то Вася не выиграет следующим ходом и, вне зависимости от ответного хода Васи, у Пети будет следующий ход, который приведет к его немедленной победе.

Помогите Пете найти количество оптимальных ходов.

Формат входного файла

В первой входного файла находятся два натуральных числа n, m (1 ≤ n, m ≤ 200) – размеры прямоугольника, содержащего все уже поставленные на поле крестики и нолики.

Следующие n строк содержат по m символов, каждый из которых равен одному из следующих: <<.>> (точка), <<X>> (заглавная латинская буква <<икс>>) или <<0>> (ноль). При этом <<.>> обозначает пустую клетку, <<X>> обозначает крестик, а <<0>> обозначает нолик. Гарантируется, что на поле находится равное число крестиков и ноликов, и ни один игрок еще не одержал победу.

Формат выходного файла

Выведите одно число – количество оптимальных ходов Пети.

Пример:

Источник: Командное школьное первенство Республики Карелия. Ноябрь 2014.

Обсудить       Отправить решение



Версия для печати