Problem S. 45. (May 2009)
S. 45. In some quiz magazines one often sees the following ``connect the letters'' game. Given an N×N square with some letters, your task is to connect identical letters in such a way that your lines neither intersect nor overlap each other. Prepare a program that connects each pair of identical letters on a board of size at most 20×20 in the above way, if possible, otherwise, it should connect as many pairs as possible according to the rules.
The first command line argument to your program specifies the name of the text file describing the board. This input file has N lines (provided that the board is of size N×N). Each line contains N characters. Letters to be connected are denoted by uppercase letters of the English alphabet (but at most 25), while empty squares are denoted by spaces.
The second command line argument to your program gives you the name of the text file into which your solution should be written. Your solution is the board full of letters: connecting lines between the given uppercase letters are denoted by the corresponding lowercase letters. If a complete solution does not exist, a message such as ``k pair(s) of letters can not be connected'' should be printed to the standard output. The output file in this case should contain only a board that is partially filled in, but with the highest possible number of pairs connected.
The source code of your program (s45.pas, s45.cpp, ...) and a short documentation (s45.txt, s45.pdf, ...) should be submitted, also describing briefly your solution and specifying the name of the developer environment to use for compiling.
Deadline expired on June 15, 2009.
7 students sent a solution. 7 points: 1 student. 6 points: 1 student. 5 points: 1 student. 4 points: 2 students. 3 points: 2 students.