@tottukki

Петя разгадывает головоломку, которая устроена следующим образом. Дана квадратная таблица размера НхН, в каждой клетке которой записана какая-нибудь английская буква. Кроме того, дан список ключевых слов. Пете нужно, взяв очередное ключевое слово, найти его в таблице. То есть найти в таблице все буквы этого слова, причем они должны быть расположены так, чтобы клетка, в которой расположена каждая последующая буква слова, была соседней с клеткой, в которой записана предыдущая буква (клетки называются соседними, если они имеют общую сторону — то есть соседствуют по вертикали или по горизонтали).

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

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

Входные данные
Во входном файле записаны два числа Н. Следующие Н строк по Н заглавных английских букв описывают ребус. Следующие М строк содержат слова. Слова состоят только из заглавных английских букв, каждое слово имеет длину от 1 до 100 символов. Гарантируется, что в таблице можно найти и вычеркнуть по описанным выше правилам все ключевые слова.

Выходные данные
В выходной файл выведите в алфавитном порядке оставшиеся в таблице буквы.

ввод:
5 3
POLTE
RWYMS
OAIPT
BDANR
LEMES
OLYMPIAD
PROBLEM
TEST

вывод:
AENRSW

Вернуться к обсуждению:
Жадный алгоритм(с++) C++

0