Preparing NOJ

抢机器

2000ms 65536K

Description:

程序设计实践周开始啦!南邮的同学们都非常激动,因为他们准备冲向机房抢占机器。我们可以把机房和同学看作一个nm列的矩阵AAij=1表示第i行第j列是一个机房,Aij=0表示该位置是一个准备抢机器的同学。当然,一个机房里面有很多机器,多个同学可以到同一个机房抢占机器。如果一个同学在x1y1列,他准备到x2y2列的机房抢机器,那么他将花费|x1-x2|+|y1-y2|的时间。每个同学都希望花费最少的时间,因为这样他们可以抢占更好的机器。求出所有同学抢机器花费最少的总时间。

Input:

第一行是一个整数T(1<=T<=10),表示共有T组数据。

对于每组数据:

第一行有两个整数NM1<=N,M<=1000)。

接下来共N行,每行M个整数,Aij0<=Aij<=1

每组数据保证至少有一个机房。

Output:

每行输出一个整数,表示所有同学抢占机器花费最少的总时间。

Sample Input:

3
2 2
0 1
0 0
2 2
0 0
1 1
3 4
1 1 1 0
1 1 0 0
0 0 0 0

Sample Output:

4
2
11

Note:

 

本题由旧版NOJ导入,来源:ym

Info

NOJ

Provider NOJ

Code NOJ1651

Tags

Submitted 2

Passed 1

AC Rate 50%

Date 04/20/2019 10:03:10

Related

Nothing Yet