[原创]Codechef Matrix Transformation 【数学】

2017-06-28 20:14:52 Tabris_ 阅读数：282

https://blog.csdn.net/qq_33184171/article/details/73863598

———————————————————————————————————————————
Chef has two n × m matrices A and B. He wants to make them completely identical, to achieve this goal, he can perform the following actions in a single move:

Choose one of the matrices, either A or B.
Choose either one row or one column of the selected matrix.
Increment all the numbers in the selected row or column by 1.
Now Chef is wondering, what is the minimal number of moves he has to perform in order to make matrices A and B equal? Or is it just impossible?

Input
The first line of the input contains an integer T denoting the number of test cases.

For each test case, the first line of input contains two integers n and m.

The following n lines contain m space separated integers each ― the matrix A.

The next n lines contain m space separated integers each ― the matrix B.

Warning! The size of the input file can be up to 10 MB!

Output
For each test case, output a single integer ― the minimal number of moves Chef has to perform in order to make matrices A and B equal or -1 if this is not possible.
Constraints
1 ≤ T ≤ 100
1 ≤ n ≤ m ≤ 105
1 ≤ n × m ≤ 105
Let us denote the sum of n × m over all T testcases by S
1 ≤ S ≤ 5 · 105
1 ≤ Aij ≤ 109
1 ≤ Bij ≤ 109
Example
Input:
3
2 2
1 1
1 1
1 2
3 4
2 2
1 9
9 1
9 1
1 9
1 4
4 5 7 1
2 3 4 5

Output:
3
-1
9
Explanation
Example case 1. We can transform the matrix A into B in three moves:
1 1 -> 1 2 -> 1 2 -> 1 2
1 1 -> 1 2 -> 2 3 -> 3 4
Example case 2. It is impossible to make these matrices equal using only the allowed moves.
Example case 3. We can transform matrix A into 4 5 7 7 in six moves and matrix B into the same 4 5 7 7 in three moves.

————————————————————————————————————————————

$a[i][j]=x[i]+y[j],$
$a[k][l]=x[k]+y[l];$

$a[i][l]=x[i]+y[l];$
$a[k][j]=x[k]+y[j];$

$a[i][j]+a[k][l]==a[i][l]+a[k][j];$
$a[i][j]+a[o][p]==a[i][p]+a[o][j];$

$a[o][p]+a[k][l]==a[o][l]+a[k][p];$

Codechef为什么这个强势，这只是个EASY难度啊啊啊啊

————————————————————————————————————————————