P16649 [GKS 2018 #D] Funniest Word Search

Siv 的生日在下周，Cel 正在为她准备生日礼物。因为 Siv 喜欢拼图，Cel 决定制作一个单词搜索谜题作为礼物。 在单词搜索谜题中，解题者会得到一个 $R$ 行 $C$ 列的矩形网格，解题者需要找出隐藏在网格中的所有有效单词。每个隐藏单词可以在网格中水平或垂直（但不能对角线）出现，可以是正向或反向。隐藏单词可以重叠。 Cel 有一个包含 $W$ 个不同单词的字典；这些单词是唯一可以隐藏在谜题网格中的单词。（当然，并非网格中每个连续的水平或垂直部分都必然包含某个隐藏单词。）这些单词不一定是真实的英语单词。每个单词可能在网格中出现一次或多次，也可能根本不出现。 Cel 已经创建好了单词搜索谜题。然而，问题在于：谜题太大，无法打印在一张纸上。由于 Siv 的生日即将到来，没有足够的时间从头创建一个新的单词搜索谜题。因此，Cel 想知道她是否可以通过简单地选择原始网格中的一个非空、与网格对齐的子网格来缩小网格尺寸。 随机选择一个子网格可能会导致谜题无聊，没有太多隐藏单词。因此，Cel 希望选择具有最大趣味值的子网格，其中子网格的趣味值定义为： 趣味值 = (匹配单词的总长度) / (子网格的宽度 + 子网格的高度) 注意： - 单词必须完整地出现在子网格中才被计入。 - 如果一个单词在子网格中出现 $x$ 次，则其长度应在上述公式中累加 $x$ 次。 - 如果一个单词及其反向都在子网格中出现（即使在相同位置！），我们也会将这两次出现都计入。 - 具有最大趣味值的子网格可能就是整个原始网格。 你能帮助 Cel 找出子网格可能的最大趣味值，以及具有该趣味值的不同子网格的数量吗？两个子网格被认为是不同的，当且仅当存在网格中的某个格子（即某个 (行, 列) 位置）只属于其中一个子网格而不属于另一个。

输入的第一行给出测试用例的数量 $T$。接下来有 $T$ 个测试用例。每个测试用例的结构如下： - 第一行包含三个整数 $R$、$C$ 和 $W$，含义如上所述。 - 接下来的 $R$ 行，每行恰好包含 $C$ 个大写英文字母。 - 接下来的 $W$ 行，每行恰好包含一个有效单词。每个单词只包含大写英文字母。

对于每个测试用例，输出一行，格式为 `Case #x: y/z n`，其中： - $x$ 是测试用例编号（从 $1$ 开始）。 - $y/z$ 是一个不可约分数，等于子网格的最大可能趣味值（如上所述）。 - $y$ 是一个非负整数。 - $z$ 是一个正整数。 - $n$ 是趣味值等于 $y/z$ 的子网格个数。 如果 $y$ 和 $z$ 的最大公约数为 $1$，则称 $y/z$ 为不可约分数。

记 $(i, j)$ 表示第 $i$ 行第 $j$ 列的格子。 在样例 #1 中，趣味值最高的子网格是整个网格。有效单词 `A` 在网格中出现 $8$ 次： - 在格子 $(1, 1)$ 处水平方向出现 $2$ 次（正向一次，反向一次）。 - 在格子 $(1, 1)$ 处垂直方向出现 $2$ 次（正向一次，反向一次）。 - 在格子 $(1, 2)$ 处出现 $4$ 次（水平和垂直方向，正向和反向各一次）。 在样例 #2 中，有 $3$ 个子网格的趣味值等于 $0$： - 仅包含一个格子 $(1, 1)$ 的子网格。 - 仅包含一个格子 $(1, 2)$ 的子网格。 - 左上角在 $(1, 1)$、右下角在 $(1, 2)$ 的子网格。 ### 限制条件 - $1 \le T \le 100$。 - $1 \le R \le 100$。 - $1 \le C \le 100$。 - 有效单词列表中没有重复的单词。 - 有效单词列表中所有单词的总长度不超过 $5000$ 个字母。 **小数据集（测试集 1 – 可见）** - 每个有效单词的长度恰好为 $1$。 - $1 \le W \le 26$。 **大数据集（测试集 2 – 隐藏）** - $1 \le W \le 1000$。 翻译由 DeepSeek V4 Pro 完成