Задача №113631. Крестики-нолики
Пете и Васе стало очень скучно на уроке биологии, и они решили поиграть в любимую всеми школьниками игру в крестики-нолики до пяти в ряд на бесконечном поле.
Рассмотрим кратко правила игры. Игра происходит на бесконечном клетчатом поле, два игрока делают ходы по очереди, первый игрок ходит крестиками, а второй — ноликами. В свой ход игрок выбирает свободную клетку поля и ставит туда свой символ. Если после хода очередного игрока на поле есть пять его символов подряд по вертикали, горизонтали или диагонали, то сделавший такой ход игрок объявляется победителем и игра заканчивается.
Петя и Вася уже довольно долго играют в игру. Сейчас должен ходить Петя, который играет крестиками. Петя надеется побыстрее завершить игру и хочет выиграть не более чем за два, а лучше за один ход. Петя называет ход оптимальным, если для этого хода выполнено одно из двух:
- этот ход приводит к немедленной победе Пети;
- не существует хода, который приводит к немедленной победе Пети, но если Петя сделает этот ход, то Вася не выиграет следующим ходом и, вне зависимости от ответного хода Васи, у Пети будет следующий ход, который приведет к его немедленной победе.
В первой входного файла находятся два натуральных числа \(n\), \(m\) (\(1 \le n, \ m \le 200\)) — размеры прямоугольника, содержащего все уже поставленные на поле крестики и нолики.
Следующие \(n\) строк содержат по m символов, каждый из которых равен одному из следующих: «.» (точка), «X» (заглавная латинская буква «икс») или «0» (ноль). При этом «.» обозначает пустую клетку, «X» обозначает крестик, а «0» обозначает нолик. Гарантируется, что на поле находится равное число крестиков и ноликов, и ни один игрок еще не одержал победу.
Выведите одно число — количество оптимальных ходов Пети.
5 3 ... 000 XXX ... ...
2
4 4 ..0. .XX0 .0X. ....
0
5 6 ...... .XXX.. .0000. ..X... ......
0