2011年9月29日 星期四

11979 - Hamming Base

給定N個以N進制表示的整數,每個整數有M個位數(包含前導的零),我們定義兩個整數為「K階相似(K-similar)」表示他們剛好有K個位數值是一樣的,例如321與213為零階相似,3456與6453與二階相似,123與453與一階相似。你的目標是一步步改變這N個整數,使得任兩個整數為零階相似,每一步限定為只能改變某個整數的某個位數,使其加一或減一,當該位數值為0則無法作減一的動作,若為N-1則無法做加一的動作。

請你用最少的步驟來達成這項目標。

Input

輸入的一開始會給定整數T(<= 50)表示測試資料的組數。每組資料的第一列有兩個整數N(2 <= N <= 2000)與M(1 <= M <= 10),接下來的N列每列有M個其值介於 0 ~ N-1 的整數,每列的M個整數組成有M個位數,且以N進制表示的整數。

Output

請每組測試資料輸出資料編號與達成這項目標的最少步驟數。

Sample Input

Output for Sample Input

2
3 3
0 0 0
0 0 0
0 0 0
4 2
0 0
0 0
0 2
2 0
Case 1: 9
Case 2: 8

沒有留言:

張貼留言