题目大意：已知n*m的矩阵每个2*2方阵四个元素的和，请还原出这个矩阵。
题目描述
Alice 有一个 n×m 的矩阵 ai,j（1≤i≤n，1≤j≤m），其每个元素为大小不超过 106 的非负整数。
Bob 根据该矩阵生成了一个 (n – 1) \times (m – 1) 的矩阵 b_{i, j}（1 \le i \le n – 1，1 \le j \le m – 1），每个元素的生成公式为
b_{i, j} = a_{i, j} + a_{i, j + 1} + a_{i + 1, j} + a_{i + 1, j + 1}
现在 Alice 忘记了矩阵 a_{i, j}，请你根据 Bob 给出的矩阵 b_{i, j} 还原出 a_{i, j}。
输入输出格式
输入格式
**本题有多组数据。**
第一行，一个整数 T，表示数据组数。对于每组数据：
第一行，两个正整数 n, m，表示矩阵 a_{i, j} 的大小。
接下来 n – 1 行，每行 m – 1 个非负整数，表示 b_{i, j}。
输出格式
对于每组数据：
1. 若矩阵 b_{i, j} 无法被生成，则输出一行一个字符串 `NO`。
2. 若矩阵 b_{i, j} 可被生成，则先输出一行一个字符串 `YES`，接下来输出 n 行每行 m 个（用单个空格分隔的）大小不超过 {10}^6 的非负整数表示 a_{i, j}。
若有多个矩阵 a_{i, j} 可生成给出的 b_{i, j}，输出其中任意一个即可。
输入输出样例
输入样例 #1
3
3 3
28 25
24 25
3 3
15 14
14 12
3 3
0 3000005
0 0
输出样例 #1
YES
7 8 8
8 5 4
4 7 9
YES
4 2 2
5 4 6
5 0 2
NO
说明
**【数据范围】**
对于所有测试数据：1 \le T \le 10，2 \le n, m \le 300，0 \le b_{i, j} \le 4 \times {10}^6。
每个测试点的具体限制见下表：
| 测试点编号 | 特殊限制 | |
|---|---|---|
| 无 | ||
| 无 |
解题思路
暴力：对于只有两列的情况，我们可以枚举第一行的和，递推后面行的和，只要和满足条件，就能分成两半，填出矩阵a。
一个2*2的方阵，只要确定其中3个元素，另一个也就定下来了。我们不妨设第一行第一列的元素的值为0，这样就可以填出一个矩阵a，满足矩阵b的限制。那么，怎样才可以满足0~1e6的限制呢？
如果a_{11}不满足条件，太小了我们可以加一个数，相邻的交替加减即可。如果同一行的数字都要加怎么办？那只能列进行减，也是交替解决。
+x1 -x1 +x1 -x1 +x1 +y1 +y2 +y3 +y4 +y5 +x2 -x2 +x2 -x2 +x2 -y1 -y2 -y3 -y4 -y5 +x3 -x3 +x3 -x3 +x3 +y1 +y2 +y3 +y4 +y5 +x4 -x4 +x4 -x4 +x4 -y1 -y2 -y3 -y4 -y5 +x5 -x5 +x5 -x5 +x5 +y1 +y2 +y3 +y4 +y5
第一行依次+x_1、-x_1、+x_1……；第一列依次+y_1、-y_1、+y_1……
这样，要让a_{11}满足条件，只需要满足0 <= a_{11}+x_1+y_1 <= 1e6，简单来说就是0 <= a +x + y <= 1e6，即x <= -x + 1e6 – a和-x <= y+a。
x和-x的关系很难描述，我们可以稍微调整一下，让其中x和y异号：
+x1 -x1 +x1 -x1 +x1 -y1 +y2 -y3 +y4 -y5 -x2 +x2 -x2 +x2 -x2 +y1 -y2 +y3 -y4 +y5 +x3 -x3 +x3 -x3 +x3 -y1 +y2 -y3 +y4 -y5 -x4 +x4 -x4 +x4 -x4 +y1 -y2 +y3 -y4 +y5 +x5 -x5 +x5 -x5 +x5 -y1 +y2 -y3 +y4 -y5
这样，每个位置的约束，要么是0 <= a+x-y <= 1e6，要么是0 <= a-x+y <= 1e6，可以转成x <= y+1e6-a和y <= x+a。我们可以当差分约束系统来做。
x编号1到n，y编号n+1到n+m，用Bell-man Ford算法，松弛n+m次必出结果。如果矩阵元素下标i+j是奇数，那么对于被减的变量x，有f[x] = min(f[x], y+a)，对于加数y，有f[y] = min(f[y], x+1e6-a)；如果i+j是奇数，则x和y反过来。如果松弛不出来则无解。另外，为了防止爆int，如果x或者y的值太小，可以直接判断无解，因为没必要某一行或者某一列减太多。
程序实现
