Contest.uni-smr.ac.ru :: соревнования по программированию
Русская версия || English version
Login:
Password:
Забыли пароль?
 пример поиска: Вася Пупкин
 

Задача D. Инверсии

Задачу добавил: alef

Успешно сдано решений: 3

Размышления Кондрата были прерваны незаметно подошедшим к нему невысоким, чуть полноватым человеком средних лет.

— Напрасный труд, чужеземец, — произнес он скрипучим, совсем непохожим на естественный голосом. — Картой можно описать мир, но не переход между мирами. Ты, верно, думаешь, что найдешь выход там, где был вход?

Кондрат смотрел на незнакомца и понимал, что произносить слова нет никакой необходимости. Он даже не был уверен, что незнакомец говорит что-либо вслух.

— Вот куда ты пошел бы сейчас? — поинтересовался незнакомец. Кондрат не хотел доставать спрятанную в одежде иголку. Незнакомец испытующе посмотрел на него: — Присмотрись — если пройти вперед еще несколько шагов, ты как раз окажешься там, откуда начал свой путь.

Кондрат видел это и сам. Он даже удивился, как сразу не узнал скамейку, раскидистое дерево: ведь это было первое, что он увидел, когда перешагнул через порог и очутился в зазеркальном городе.

— Ну, так что говорит твой компас? — незнакомец явно знал про иголку. Вздохнув, Кондрат вытащил ее, положил на лист бумаги и начал нашептывать заветные слова. Иголка лишь чуть дрогнула. Кондрат прошел несколько шагов в этом направлении, держа лист бумаги с иголкой на ладони. Вдруг иголка резко позвернулась в прямо противоположном направлении. Кондрат ходил так несколько минут. Незнакомец, молча наблюдавший за происходящим, наконец, сказал:

— Пожалуй, я расскажу тебе, как отсюда вернуться. Похоже, у тебя и впрямь нет дурных мыслей. Можешь называть меня Рагнар.

Рагнар рассказал Кондрату, что в городе есть сеть порталов, каждый из которых помечен определенным кодом. Этот код — полоска из N клеток, часть из которых покрашена в черный цвет, а часть — в белый. Когда кто-либо попадает через один из порталов в зазеркальный город, он становится носителем кода того портала, через который прошел.

Чтобы вернуться обратно, нужно пройти через несколько других порталов таким образом, чтобы «перекрасить» все черные клетки в белый цвет во входном коде. Клетки перекрашиваются по следующим правилам.

Если на месте #J во входном коде и коде портала стоят клетки разного цвета, то после прохода через портал клетка входного кода станет (или останется) белой.

Если на месте #J во входном коде и в коде портала стоят клетки одинакового цвета, то после прохода через портал цвет клетки входного кода станет (или останется) черным.

Ваша задача — по заданным кодам порталов получить последовательность их прохождения.


Формат входного файла input.txt

Первая строка — целые числа N и M (1 N, M 100) — количество клеток в коде каждого портала и количество порталов.

Следующие M строк содержат по N символов B и W, где B — клетка черного цвета, W — клетка белого цвета.

В первой из этих M строк указан код портала, через который прошел в зазеркальный город Кондрат


Формат выходного файла output.txt

Первая строка — целое число Z — количество порталов, которые придется пройти Кондрату, прежде чем все клетки в его входном коде окажутся перекрашенными.

Вторая строка — Z целых чисел через пробел — номера порталов в той последовательности, в которой он должен через них проходить.

Количество порталов не обязательно должно быть минимальным, но ни один портал не должен встречаться в последовательности более одного раза.

Если выйти из зазеркального города невозможно, выходной файл должен состоять из одной строки, в которой следует вывести –1


Пример входного файла — 1

3 5

BBW

BBW

WWW

WBB

WWB


Пример выходного файла — 1

2

3 1


Пример входного файла — 2

6 6

BWWWWW

WWWBWW

WWBWWW

WBWWWW

WWWWWB

WWWWBW


Пример выходного файла — 2

5

2 3 4 5 6


Пример входного файла — 3

5 5

WWBWW

WBWWW

BWWWW

WWWWB

WWWBW


Пример выходного файла — 3

-1


Сдать задачу

Задать вопрос жюри по этой задаче