1192. 纵横填字游戏

【问题描述】

这个题目要求你编写一个程序来解决一个纵横填字游戏。

这个游戏比我们在报纸上见到的通常的填字游戏要简单。游戏仅给出单词的起始位置，方面(横向或纵向)以及单词的长度。只要单词的长度正好，游戏中能填入任何一个来自词典的单词。

在游戏中单词相交处的字母必须相同，当然，任何单词只准使用一次。

思考一下以下这个游戏。

例如，假定从上到下有5行，用0到4来表示，从左到右有5列，用0到4来表示。我们用(X, Y)来表示填字游戏中第X列和第Y行的字母。

在这个游戏中，我们需填入5个单词：在(0, 0)的右边填入一个4个字母的单词，在(0, 0)的下方填入一个4个字母的单词，在(2, 0)的下方填入一个4个字母的单词，在(0, 2)的右边填入一个3个字母的单词，最后在(2, 3)的右边填入一个3个字母的单词。字典上所有的单词都能使用但最多只能使用一次。例如，以下是一个可能的解决方案。

（0, 0）右边，LATE

（0, 0）下面，LIED

（2, 0）下面，TELL

（2, 3）右边，LOW

【输入格式】

输入的第一行包含一个整数n(n≤15)，表示要填的单词的数量。

接下来的n行中每行给出关于一个单词的提示，在每个提示中分别给出单词的首字母在填字游戏中的列和行的位置，后面根据单词的方向是横向还是纵向，相应跟字符A或字符D，最后一个数表示该单词的长度，以上数据之间均用空格隔开。

接下来若干行，每行一个单词(所含的字母可以是大写或小写)，表示字典。

你能作以下的进一步的假设。

（1）填字游戏的尺寸不超过10×10。

（2）游戏盘中放得下所有的单词。

（3）用给定的词典是能够破解出该游戏的。

（4）字典有最多不超过100000个单词，并且按词典顺序存储。

（5）字典中所有单词的长度不超过20个字符。

【输出格式】

输出应该包含n行，输出游戏中可填入的所有单词。

单词应该每行出现一个，并且按输入文件中提示的顺序输出。每个单词中所有的字母必须是大写的。所有的单词必须来自给定的词典文件(忽略大小写)。任何单词只能使用一次。对于给定输入文件可能有大量的正确解决方案，你只须输出其中的任意一个解决方案。

【输入样例】

5
0 0 A 4
0 0 D 4
2 0 D 4
0 2 A 3
2 3 A 3
若干单词

【输出样例】

LATE
LIED
TELL
EEL
LOW

【提示】

输入文件虽然已经排好序，但是全部转换为大写字母后，不一定是排好序的。