#P1673. 旋转圆柱矩阵

旋转圆柱矩阵

将圆柱体的侧面展开能得到一个m*n的矩形。这是姑且看成一个01矩阵, 我们需要通过特定的移动得到另一个矩阵(该矩阵其中任意的某一列全部为1),每一次只能移动一行,且只能移动一位,可以向左移动,也可以向右移动,求最小的移动步数,如不能通过移动得到结果,则输出“-1”。
例如:
3*5的矩阵
00001
10000
00001
我们只需要将第二行向左移动一位即可得到所求。

Input

第一行一个整数N(N<=10),表示测试数据的组数。
第二行两个整数m n( 1 <= n , m <= 200),表示矩阵的行数和列数。
接下来m行,其中每一行n个数字。

Output

如果该矩阵可以移动得到结果,则每行一个数字,表示最小的移动步数。
否则输出-1。

Sample Input

2
3 5 
00001
10000
00001
3 4 
0001
0100
0001

Sample Output

</p>
1
2

HINT

Source