← 返回题目列表

Codeforces · 1676/C

C. 最相似的词

中文机器翻译题面 查看原题

给你 $$$n$$$ 个长度相等的单词 $$$m$$$,由小写拉丁字母组成。第 $$$i$$$ 个单词表示为 $$$s_i$$$。

在一次操作中,您可以选择任何单个单词中的任何位置,并将该位置的字母更改为按字母顺序排列的上一个或下一个字母。例如:

- 您可以将“e”更改为“d”或“f”;
- 'a' 只能更改为 'b';
- 'z' 只能更改为 'y'。

两个单词之间的差异是使它们相等所需的最小移动次数。例如,“最佳”和“成本”之间的差异为 $$$1 + 10 + 0 + 0 = 11$$$。

求 $$$s_i$$$ 和 $$$s_j$$$ 的最小差值,使得 $$$(i < j)$$$。换句话说,找到所有可能的 $$$n$$$ 单词对的最小差异。

输入

输入的第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 100$$$) — 测试用例的数量。测试用例的描述如下。

每个测试用例的第一行包含 $$$2$$$ 整数 $$$n$$$ 和 $$$m$$$ ($$$2 \leq n \leq 50$$$, $$$1 \leq m \leq 8$$$) — 分别是字符串的数量和长度。

接下来是 $$$n$$$ 行,其中第 $$$i$$$ 包含长度为 $$$m$$$ 的单个字符串 $$$s_i$$$,由小写拉丁字母组成。

输出

对于每个测试用例,打印一个整数 - 给定字符串的所有可能对的最小差异。

示例

输入 #1

6
2 4
best
cost
6 3
abb
zba
bef
cdu
ooo
zzz
2 7
aaabbbc
bbaezfe
3 2
ab
ab
ab
2 8
aaaaaaaa
zzzzzzzz
3 1
a
u
y

输出 #1

11
8
35
0
200
4

注意

对于第二个测试用例,可以显示最佳配对是 ("abb","bef"),其差异等于 $$$8$$$,可以通过以下方式获得:在一次移动中将第一个字符串的第一个字符更改为 'b',在 $$$3$$$ 移动中将第二个字符串的第二个字符更改为 'b',在 $$$3$$$ 移动中将第二个字符串的第三个字符更改为 'b' $$$4$$$ 移动,因此总计 $$$1 + 3 + 4 = 8$$$ 移动。

对于第三个测试用例,只有一对可能的,可以证明使字符串相等所需的最小移动量是 $$$35$$$。

对于第四个测试用例,有一对字符串已经相等,因此答案是 $$$0$$$。