Вступление
В славном городе Урюпинске по случаю открытия нового Дворца Культуры «Колхозник» было решено организовать международный турнир по шашкам. На турнир съехались лучшие игроки из Бердичева, Жмеринки и Тмутаракани, а также известный гроссмейстер О. Бендер из Албании.
Задача
Наибольший интерес общественности вызвала партия между г-ном Бендером и председателем местного колхоза «Путь Ильича» Вениамином Козловым. Гроссмейстер играл белыми, а председатель молча. После очередного хода противника г-н Бендер заявил, что может выиграть партию, срубив все чёрные шашки за один ход. Г-н Козлов изучил позицию на доске и предложил поспорить на бутылку минеральной воды «Ессентуки», что это невозможно.
Председателю колхоза было невдомёк, что г-н Бендер владеет уникальным тактическим приёмом. А именно, способностью незаметно убирать с доски произвольное количество шашек любого цвета. К чести гроссмейстера нужно заметить, что он старается играть честно и всегда убирает с доски минимальное количество шашек. А сколько шашек г-н Бендер должен убрать на этот раз?
Исходные данные
Каждая из 8 строк содержит 8 символов соответствующие клетки доски. Символ «W» обозначает белую шашку, символ «B» чёрную шашку, а символ «.» (точка) свободную клетку. На доске присутствуют не менее одной и не более двенадцати шашек каждого цвета. Все шашки располагаются в клетках одного цвета. Белые шашки, достигшие восьмой горизонтали, и чёрные шашки, достигшие первой горизонтали, по-прежнему считаются шашками, т.е. дамок на доске нет.
Результат
Вывести искомое количество шашек.
Пример
исходные данные | результат |
---|
W.......
.W......
..B...B.
.....W..
..B.B...
........
........
........
| 1
|
Замечания
Шашечная доска это чёрно-белая доска размером 8*8 клеток. Клетка в левом нижнем её углу имеет координаты (1, 1), а клетка в правом верхнем углу координаты (8, 8). Клетка с координатами (x, y) белая, если (x+y) modulo 2 = 1, иначе клетка чёрная.
За один ход шашка может последовательно срубить произвольное количество шашек противника. Шашка, находящаяся в клетке с координатами (xi, yi) может срубить шашку противника, находящуюся в клетке с координатами (xj, yj), если abs(xj-xi) = abs(yj-yi) = 1, 2 ≤ xj ≤ 7, 2 ≤ yj ≤ 7, и клетка с координатами (2*xj-xi, 2*yj-yi) свободна. При этом шашка перемещается из клетки с координатами (xi, yi) в клетку с координатами (2*xj-xi, 2*yj-yi), а срубленная шашка противника снимается с доски.
В примере г-н Бендер должен незаметно убрать с доски чёрную шашку, находящуюся в клетке с координатами (7, 6). Тогда белая шашка, находящаяся в клетке с координатами (6, 5), последовательно срубит все оставшиеся чёрные шашки, находящиеся в клетках с координатами (5, 4), (3, 4) и (3, 6).
Автор задачи: Никита Рыбак, Илья Гребнов, Дмитрий Ковалёв
Источник задачи: Timus Top Coders: Third Challenge