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
hide comments
nadstratosfer:
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).
|
|
Jimmy Tirtawangsa:
2018-10-11 04:01:09
Max score is 100 |
|
dewa251202:
2018-10-10 13:29:12
what will be the max score? |
Added by: | Jimmy Tirtawangsa |
Date: | 2018-08-30 |
Time limit: | 1s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All |