Шахматная мастерская
(Время: 1 сек. Память: 16 Мб Сложность: 30%)
Хозяин мастерской по изготовлению шахматных досок гроссмейстер Хосе Раулевич Капабланка был очень зол. «Ну, кто так раскрашивает доски?! Ну скажи мне, Бобби, разве я тебя так учил раскрашивать доски?!» - спрашивал он у своего подмастерья.
А дело было вот в чем. Недавно его мастерская получила заказ на изготовление нестандартной шахматной доски размером N на M . Саму шахматную доску из дорогой породы дерева он изготовил, а раскрасить ее поля он поручил своему подмастерью и ученику Бобби. Бобби, однако, справился с этой задачей очень плохо. Он раскрасил доску так, что некоторые соседние поля оказались покрашенными в один цвет. А такого на шахматной доске никогда не было, и быть не может!
Теперь у Бобби есть всего одна ночь на исправление своей ошибки. Казалось бы, времени много. Но все усложняется тем, что перекрасить поле шахматной доски достаточно сложная задача, ведь надо аккуратно снять старый слой краски. Поэтому Бобби хочет перекрасить наименьшее возможное число полей. Помогите ему написать программу, которая найдет: какие поля доски ему надо перекрасить.
Единственным требованием к шахматной доске, которая должна получиться в результате, является то, что любые два соседних поля покрашены в разные цвета. Ну, и, конечно, любое поле должно быть либо белым, либо черным.
Соседними полями на шахматной доске Хосе Раулевич считает поля, имеющие общую сторону.
Входные данные
Первая строка входного файла INPUT.TXT содержит два целых числа: N и M (1 ≤ N, M ≤ 100). Далее идут N строк по M символов в каждой. j-ый символ i-ой из этих строк равен W, если Бобби покрасил соответствующее (т.е. находящееся на пересечении i-ой горизонтали и j-ой вертикали) поле в белый цвет, и B, если в черный.
Выходные данные
В первой строке выходного файла OUTPUT.TXT выведите минимальное количество k полей, которые должен перекрасить Бобби.
Далее выведите k строк, описывающих поля, которые он должен перекрасить. Описание каждого поля должно состоять из двух чисел: i и j (1 ≤ i ≤ N, 1 ≤ j ≤ M), задающих горизонталь и вертикаль, на пересечении которых находится данное поле.
Ни одно поле не должно быть указано в этом списке дважды. Может оказаться так, что k = 0, и Хосе Раулевич зря кричал на Бобби. Впрочем, это объясняется тем, что гроссмейстер уже весьма стар и его зрение далеко не идеально.
Примеры
| № | INPUT.TXT | OUTPUT.TXT |
|---|
| 1 | 4 4
BBBB
BBBB
BBBB
BBBB | 8
1 1
1 3
2 2
2 4
3 1
3 3
4 2
4 4 |
| 2 | 3 3
WBW
BWB
WBW | 0 |
Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!
| 
