TTS2018 - Crosswords

Given input a set of k words and a matrix m x n of letters. Find all words in the matrix formed as sequence of neighboring letters. In the matrix, every letter is a neighbor to 8 other letters. Every word can't use the same matrix element more than once. A matrix element can be used in more than one word, though.

eg. given the words = {"kucing", "dalam", "karung"} and matrix 3x4 as follow:

k a r d
u c u g
m i n l

Starting from letter k, down once, right once, down again once, then right once, and up right diagonal once yields "kucing". Once again, starting from letter k, right twice, down twice, then up right diagonal once, yields "karung". As no other choice, words in the matrix are {"kucing", "karung"}.

Input

Every data contains in three lines. First line has three numbers::number of words in the set (k), rows (m) and columns  (n) of the matrix. It is guaranteed that 1 <= k <= 10 and 1 <= m, n <= 7 with each word is less then 50 letters.
Second line contains k words, separated by one space.
The last line contains mn letters, separated by one space, The letters will form the matrix m x n.

Output

Output are words from the set that can be found in the matrix using the above criteria.
Put the output in one line, words are separated by one space, in the same order as from the set.
If no word in the set was found, write a single dash ("-") as the output.

Example

Input:
3 3 4
kucing dalam karung
k a r d u c u g m i n l Output: kucing karung

--------

Diberikan input sekumpulan k kata-kata dan matrik m x n huruf-huruf. Cari semua kemungkinan kata yang dapat terbentuk dari rangkaian huruf yang berdampingan dalam matrik. Didalam matrik. setiap huruf berdampingan dengan 8 huruf lain. Setiap kata tidak boleh menggunakan suatu elemen matrik lebih dari satu kali, tetapi satu elemen matrik dapat digunakan oleh lebih dari satu kata.

Misalnya, diberikan kamus={ "kucing", "dalam" "karung" } dengan matrik tts (3x4) sbb:
k a r d
u c u g
m i n l

Dimulai dari huruf k, turun 1x, ke kanan 1x, turun lagi 1x, ke kanan 1x, dan naik miring ke kanan 1x, diperoleh "kucing". Sekali lagi, dimulai dari huruf k, ke kanan 2x, turun 2x, dan naik miring ke kanan 1x, diperoleh "karung". Karena tidak ada pilihan lain lagi, maka kata-kata yang dapat diperoleh adalah { "kucing", "karung" }.

Input

Setiap data coba terdiri dari tiga baris. Baris pertama berisi 3 buah bilangan: jumlah kata dalam kamus (k), baris (m) dan kolom (n) dari tts. Diberikan jaminan bahwa 1 <= k <= 10 dan 1 <= m, n <= 7 dengan tiap kata akan kurang dari 50 huruf.
Baris kedua berisi k kata yang terpisahkan oleh satu spasi.
Baris terakhir berisi mn huruf yang terpisahkan oleh satu spasi, membentuk tts berukuran m x n.

Output

Output adalah kata-kata dalam kamus yang dapat dibentuk dari huruf-huruf dalam matrik sesesuai kriteria diatas.
Output hanya satu baris, kata-kata dipisahkan satu spasi, sesuai dengan urutan dalam kamus.
Jika tidak satupun kata dalam kamus diperoleh dalam tts, outputkan satu simbol dash (tanda minus, "-") dalam baris output.

Contoh

Input:
3 3 4
kucing dalam karung
k a r d u c u g m i n l Output: kucing karung

Added by:Jimmy Tirtawangsa
Date:2018-08-30
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All

hide comments
2020-07-16 00:05:31
There is something wrong with half of the input files in this problem, but it's next to impossible to identify because of judge used (eg. failed assert gives 0p for single case, but triggering an infinite loop results in overall WA).

Spare yourself the frustration and solve ALLIZWEL instead.

Last edit: 2020-07-16 00:12:42
2018-10-11 04:01:09 Jimmy Tirtawangsa
Max score is 100
2018-10-10 13:29:12
what will be the max score?
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.