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