1007:找单词游戏

时间限制: 1 S | 内存限制: 65536 KB
Accept: 41 | Submit: 102
[提交] [状态] [讨论版]
描述

有一个由N*N个字母组成的图,ZSW小盆友就爱做无聊的游戏,给他一些单词,从图中找到这些单词,每个字母最多被使用一次,并计算出除了这些被使用的字母外,还剩下多少个字母未被使用。

例如:给定一个3*3的字母图

B

E

 G

E

  G

 A

G

X

 Y

2个单词beg,gay要输出除了这两个单词外剩下的字母个数

此例题可以

B       _       G            B       E       G              B       _       G

E       _       A            _       G      A                E       G      A

G      _       Y             _      _       Y                _       _       Y

3 _ 输出3

保证给出的所有单词组合至少有一解。

输入

此题包含多组测试数据,第一行输入casecase为有case组测试数据。

  每组测试数据第一行输入2个数nmn为该字母图由n*n组成(3<=n<=50)m为给出m个单词(0<=m<=40,每个单词长度随意)。接下输入来n,每行有n个字母,接下来m行每行输入一个单词

输出

输出第几组测试数据,加“ : ”,再加剩下的字母个数。例如第一组测试数据,剩下字母个数为3则输出“1 : 3”,每组数据输出结束输出一个换行。

样例输入

1

3 2

BEG

EGA

GXY

BEG

GAY

样例输出

1 : 3

HINT
Mon Boom
来源
formicary