Задача 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