time limit per test
2 seconds
memory limit per test
256 megabytes
You are given nn words of equal length mm, consisting of lowercase Latin alphabet letters. The ii-th word is denoted sisi.
In one move you can choose any position in any single word and change the letter at that position to the previous or next letter in alphabetical order. For example:
- you can change 'e' to 'd' or to 'f';
- 'a' can only be changed to 'b';
- 'z' can only be changed to 'y'.
The difference between two words is the minimum number of moves required to make them equal. For example, the difference between "best" and "cost" is 1+10+0+0=111+10+0+0=11.
Find the minimum difference of sisi and sjsj such that (i<j)(i<j). In other words, find the minimum difference over all possible pairs of the nn words.
Input
The first line of the input contains a single integer tt (1≤t≤1001≤t≤100) — the number of test cases. The description of test cases follows.
The first line of each test case contains 22 integers nn and mm (2≤n≤502≤n≤50, 1≤m≤81≤m≤8) — the number of strings and their length respectively.
Then follows nn lines, the ii-th of which containing a single string sisi of length mm, consisting of lowercase Latin letters.
Output
For each test case, print a single integer — the minimum difference over all possible pairs of the given strings.
Example
Input
Copy
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
Output
Copy
11 8 35 0 200 4
Note
For the second test case, one can show that the best pair is ("abb","bef"), which has difference equal to 88, which can be obtained in the following way: change the first character of the first string to 'b' in one move, change the second character of the second string to 'b' in 33 moves and change the third character of the second string to 'b' in 44 moves, thus making in total 1+3+4=81+3+4=8 moves.
For the third test case, there is only one possible pair and it can be shown that the minimum amount of moves necessary to make the strings equal is 3535.
For the fourth test case, there is a pair of strings which is already equal, so the answer is 00.
每次测试的时间限制为 2 秒
每次测试的内存限制为 256 兆字节
您将获得 n
个长度相等的单词，每个单词由小写拉丁字母组成。第 i 个单词表示为 si
。
在一次移动中，您可以选择任何单个单词中的任何位置，并将该位置的字母更改为字母顺序中的前一个或下一个字母。例如：
您可以将“e”更改为“d”或“f”；
“a”只能更改为“b”；
“z”只能更改为“y”。
两个单词之间的差异是使它们相等所需的最少移动次数。例如，“best”和“cost”之间的差异为 1+10+0+0=11
。
找出 si
和 sj
的最小差异，使得 (i<j)
。换句话说，找出 n
个单词的所有可能对的最小差异。
输入
输入的第一行包含一个整数 t
(1≤t≤100
) — 测试用例的数量。测试用例的描述如下。
每个测试用例的第一行包含 2
个整数 n
和 m
(2≤n≤50
, 1≤m≤8
) — 分别表示字符串的数量和长度。
接下来是 n
行，其中第 i
行包含一个长度为 m
的字符串 si
，由小写拉丁字母组成。
输出
对于每个测试用例，打印一个整数 — 给定字符串的所有可能对的最小差值。
示例
输入副本
6
2 4
最佳
成本
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
输出副本
11
8
35
0
200
4
注意
对于第二个测试用例，可以证明最佳对是 ("abb","bef")，其差值等于 8
，可以通过以下方式获得：在一步内将第一个字符串的第一个字符更改为 'b'，在 3
步内将第二个字符串的第二个字符更改为 'b'，在 4
步内将第二个字符串的第三个字符更改为 'b'，因此总共需要 1+3+4=8
步。
对于第三个测试案例，只有一对可能的字符串，并且可以证明使字符串相等所需的最少移动次数是 35
。
对于第四个测试案例，有一对字符串已经相等，因此答案是 0
。
代码：
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <climits>
using namespace std;
int minimumDifference(int n, int m, const vector<string>& strings) {
int min_diff = INT_MAX;
for (int i = 0; i < n; ++i) {
for (int j = i + 1; j < n; ++j) {
int diff = 0;
for (int k = 0; k < m; ++k) {
diff += abs(strings[i][k] - strings[j][k]);
}
min_diff = min(min_diff, diff);
}
}
return min_diff;
}
int main() {
int t;
cin >> t;
while (t--) {
int n, m;
cin >> n >> m;
vector<string> strings(n);
for (int i = 0; i < n; ++i) {
cin >> strings[i];
}
cout << minimumDifference(n, m, strings) << endl;
}
return 0;
}