携程决赛.doc

Crossword
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 0 Accepted Submission(s): 0
Problem Description
Crossword是风靡一时的游戏,公司曾经设下神秘大奖举办了第四十届Crossword大赛,引来无数工程师注目,神秘大奖会被授予第一个准确地完成Crossword并提交的选手。参赛选手会接受如下的挑战,谜面千奇百怪,几乎无法破解!

好在聪明的工程师找到了破解的方法:为了缓解服务器的压力,Crossword的提交分成两部分,第一部分是本地验证,每个单词都会预先计算一个Hash值,本地验证会检查选手填入的每个单词的Hash值是否和预先计算的相符。如果本地验证不通过,就不会请求服务器验证。第二部分是服务器验证,通过本地验证的Solution会被提交到服务器,服务器检查每个单词是否完全相同。第一个通过检查的就是大奖赛最终的赢家了。为了大奖,工程师已经提前破解出了Hash计算的机制:
foreach ch in word
hashcode=(hashcode*33+ch)%997
你能帮助工程师,在比赛开始之后迅速地找到答案吗?上面的问题的答案如下:

Input
第一行两个整数N,M (10<=N<=30, 1<=M<=100) 表示有一个N*N的Crossword,其中有M个单词要填;
接下来的M行,每行输入五个整数x1,y1,x2,y2,k
其中x1,y1是该单词的起始位置,x2,y2是其终止位置,k代表它的hash值
然后输入一个整数K(K<10000)
接下来的K行,每行一个单词,保证Crossword上的单词一定出现在单词列表里
有多组输入输出,当N,M为0时,退出
Output
输出一个N*N的矩阵,用空格表示不需要填的字符,其他为crossword的答案。两组输出中间有一个空行。
注意,所有的Crossword保证只有唯一解。不同的输入包含不同的Layout,即单词出现的位置和长度都有可能会有改变。
Sample Input
13 28
1 1 1 7 207
1 9 1 13 982
3 1 3 7 652
3 9 3 13 494
5 1 5 5 569
5 7 5 13 903
7 1 7 6 179
7 8 7 13 146
9 1 9 7 389
9 9 9 13 680
11 1 11 5 23
11 7 11 13 429
13 1 13 5 784
13 7 13 13 234
1 1 5 1 111
7 1 13 1 145
1 3 5 3 373
7 3 13 3 940
1 5 7 5 777
9 5 13 5 626
1 7 6 7 256
8 7 13 7 405
1 9 5 9 46
7 9 13 9 8
1 11 7 11 859
9 11 13 11 972
1 13 5 13 974
9 13 13 13 268
28
onshell
charm
borscht
alien
t