ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила

1458. Военные учения

Ограничение времени: 1.0 секунды
Ограничение памяти: 64 МБ

Вступление

Однажды министр обороны Советской Федерации товарищ Иванов задумал провести широкомасштабные учения вооружённых сил Федерации. Планировалось осуществить уникальное по своей сложности десантирование - выброс бронетехники и спецназа прямо на голову воображаемым террористам. "Мы раздавим международный терроризм", - пояснил министр.
Ответственным за проведение учений был назначен генерал Шульман. Он начал с того, что поставил все выделенные на эти цели деньги на красное. После этого генерал решил отказаться от дорогостоящей десантной операции и вернуться к традиционной схеме проведения учений.

Задача

Обычно для проведения учений используется квадратный плац размером N*N клеток. Клетка, находящаяся на пересечении i-й горизонтали и j-й вертикали плаца имеет координаты (i, j). В каждой клетке находится солдат. Любой солдат Советской Армии может пребывать в одном из двух противоположных положений - "Упор лёжа" или "Строевая стойка". Начальник учений (в данном случае это сам г-н Шульман) стоит на трибуне перед плацем и время от времени истошно орёт: "Клетка (i, j)!" По этой команде все солдаты, находящиеся на i-й горизонтали или на j-й вертикали (кстати, таких солдат всегда оказывается в точности 2*N-1), изменяют свои положения на противоположные.
В начале учений каждый солдат будет находиться в произвольном начальном положении C[i, j], которое определит сам министр Иванов. А г-ну Шульману с помощью некоторой последовательности команд придётся заставить всех солдат принять одинаковое положение. Без разницы, какое именно, главное - в армии всё должно быть единообразно. В учебнике по тактике написано, что такая схема позволяет оценить умственные способности и командирские навыки высшего командного состава Советской Армии.
Генерал сильно сомневается в своих умственных способностях (да и в командирских навыках тоже) и хочет воспользоваться помощью прапорщика Шкурко. За бутылку водки прапорщик готов для любой начальной позиции найти последовательность команд, выполнение которых позволит г-ну Шульману сохранить лицо в глазах министра. Более того, за дополнительную бутылку г-н Шкурко согласился отыскать последовательность, состоящую из минимально возможного количества команд.

Исходные данные

Первая строка содержит целое чётное число N (2 ≤ N ≤ 1000). Каждая из следующих N строк содержит N символов C[i, j]. Символ "W" соответствует положению "Упор лёжа", а символ "B" - положению "Строевая стойка".

Результат

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

Пример

исходные данныерезультат
4
WBWB
BWWW
WWBW
WBWB
2
2 3
3 1
Автор задачи: Дмитрий Ковалёв, Никита Рыбак, Илья Гребнов. Благодарим Сергея Софронова за идею
Источник задачи: Timus Top Coders: Second Challenge