Problem I. 241. (May 2010)
I. 241. In certain quizzes contestants have to find one or more strings on a board of letters. We know that cells of consecutive letters in a word always have a common edge, further, no letter can be repeated within one word.
The first command line argument to your program is the name of the file containing the character table to be searched. The first line of this file contains the size of the board (number of lines and columns, separated by a space), further lines then contain the actual characters (with a space character between them). The number of lines and columns are at most 10, characters are lowercase letters from the English alphabet.
The second command line argument to your program is the name of the file containing the words to be found. The first line contains the number of strings. Strings (of length at most 30 characters, one string per line) themselves are found in the next several lines. There are at most 20 strings, comprising lowercase letters from the English alphabet.
The third command line argument to your program is the name of the file to be created. This file should contain the strings found in the board. The word list file (that is, the file given by the second command line argument) should specify the order of the strings and corresponding modified boards appearing in the third file. Strings found should be highlighted by uppercase letters. If a string occurs more than once, you should give exactly one (but an arbitrary) occurrence. Solutions should be separated by exactly one empty line.
The source code and project files of your solution -- without the .exe or any other auxiliary files generated by the compiler -- should be submitted together with a short documentation (i241.txt, i241.pdf, ...) in a compressed folder i241.zip.
The sample files tablazat.txt (the character table), szavak.txt (the words to be found) and eredmeny.txt (the results) contain some simple examples.
tablazat.txt
5 7
z v c a e l c
a a s c y x d
k k a l c l l
d o m a t e k
l w a q w l w
szavak.txt
2
matek
komal
eredmeny.txt
matek
z v c a e l c
a a s c y x d
k k a l c l l
d o M A T E K
l w a q w l w
komal
z v c a e l c
a a s c y x d
k K A L c l l
d O M a t e k
l w a q w l w
(10 pont)
Deadline expired on June 10, 2010.
Sorry, the solution is available only in Hungarian. Google translation
A feladat alapjában véve nem tűnt nehéznek - a kitűző oldaláról nézve.
A megoldók többsége egyszerű visszalépéses algoritmust használt, de a megvalósításba mindenkinél csúszott egy-két hiba.
A következő teszteseteket használtuk.
Statistics:
5 students sent a solution. 8 points: 3 students. 2 points: 1 student. 1 point: 1 student.
Problems in Information Technology of KöMaL, May 2010