Description
Blinker最近喜欢上一个奇怪的游戏。 这个游戏在一个 N*M 的棋盘上玩，每个格子有一个数。每次 Blinker 会选择两个相邻
的格子，并使这两个数都加上 1。 现在 Blinker 想知道最少多少次能使棋盘上的数都变成同一个数，如果永远不能变成同
一个数则输出-1。Input
输入的第一行是一个整数T，表示输入数据有T轮游戏组成。 每轮游戏的第一行有两个整数N和M， 分别代表棋盘的行数和列数。
接下来有N行，每行 M个数。Output
对于每个游戏输出最少能使游戏结束的次数，如果永远不能变成同一个数则输出-1。
对网格进行黑白染色【i+j&1==1为1】设最后的数为x，有n1 * x-s1=n2 * x-s2。当m，n均为奇数，即n1!=n2，方程有唯一解，验证即可。若n1=n2，若s1!=s2则无解，否则容易发现答案可以二分【把所有位置配对+1即可】。
验证解的时候，按黑白点分成二部，以当前值与目标值的差向源或汇连边，相邻的黑白点连无穷大，检验是否满流。
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define LL long long
const int s=1690,t=1691;
const LL oo2=1e17,oo1=1e13,oo3=1e15;
int a[50][50],num[50][50],xx[]={
0,0,1,-1},yy[]={
1,-1,0,0},
fir[1700],ne[10010],to[10010],que[1700],f[1700],
m,n,tot;
LL w[10010];
bool ok(int x,int y)
{return x>=1&&x<=n&&y>=1&&y<=m;
}
void init()
{int i,j;scanf("%d%d",&n,&m);for (i=1;i<=n;i++)for (j=1;j<=m;j++)scanf("%d",&a[i][j]);
}
void add(int u,int v,LL x)
{tot++;ne[tot*2]=fir[u];fir[u]=tot*2;to[tot*2]=v;w[tot*2]=x;ne[tot*2+1]=fir[v];fir[v]=tot*2+1;to[tot*2+1]=u;w[tot*2+1]=0;
}
bool find()
{int hd=1,tl=1,i,u,v;que[1]=s;memset(f,0,sizeof(f));f[s]=1;while (hd<=tl){u=que[hd++];for (i=fir[u];i;i=ne[i])if (w[i]&&!f[v=to[i]]){f[v]=f[u]+1;que[++tl]=v;}}return f[t];
}
LL dfs(int u,LL lim)
{int i,v;LL ret=0,x;if (u==t) return lim;for (i=fir[u];i&&ret<lim;i=ne[i])if (w[i]&&f[v=to[i]]==f[u]+1){x=dfs(v,min(lim-ret,w[i]));ret+=x;w[i]-=x;w[i^1]+=x;}if (!ret) f[u]=0;return ret;
}
bool ok(LL x)
{int i,j,kk,x1,y1;tot=0;memset(fir,0,sizeof(fir));for (i=1;i<=n;i++)for (j=1;j<=m;j++)if (i+j&1) add(s,num[i][j],x-a[i][j]);else add(num[i][j],t,x-a[i][j]);for (i=1;i<=n;i++)for (j=1;j<=m;j++)if (i+j&1)for (kk=0;kk<4;kk++)if (ok(x1=i+xx[kk],y1=j+yy[kk]))add(num[i][j],num[x1][y1],oo3);
// for (i=1;i<=1691;i++)
// for (j=fir[i];j;j=ne[j])
// if (w[j])
// printf("%d->%d:%lld\n",i,to[j],w[j]);while (find()){
// for (i=1;i<=1691;i++)
// for (j=fir[i];j;j=ne[j])
// if (w[j])
// printf("%d->%d:%lld\n",i,to[j],w[j]);
// system("pause");int xxx;xxx=1;while (dfs(s,oo2));}for (i=fir[s];i;i=ne[i])if (w[i]) return 0;return 1;
}
void solve1()
{int i,j;LL s0=0,s1=0,x;for (i=1;i<=n;i++)for (j=1;j<=m;j++)if (i+j&1) s1+=a[i][j];else s0+=a[i][j];x=s0-s1;for (i=1;i<=n;i++)for (j=1;j<=m;j++)if (a[i][j]>x){printf("-1\n");return;}if (!ok(x)) printf("-1\n");else printf("%lld\n",(x*m*n-s0-s1)/2);
}
void solve0()
{int i,j;LL s0=0,s1=0,x,l,r,mid;for (i=1;i<=n;i++)for (j=1;j<=m;j++)if (i+j&1) s1+=a[i][j];else s0+=a[i][j];if (s0!=s1){printf("-1\n");return;}l=0;for (i=1;i<=n;i++)for (j=1;j<=m;j++)l=max(l,(LL)a[i][j]);r=oo1;while (l<r){mid=(l+r)/2;if (ok(mid)) r=mid;else l=mid+1;}if (l==oo1) printf("-1\n");else printf("%lld\n",(l*m*n-s0-s1)/2);
}
int main()
{//freopen("in.txt","r",stdin);int T,i,j;for (i=1;i<=40;i++)for (j=1;j<=40;j++)num[i][j]=i*40+j;scanf("%d",&T);while (T--){init();if (m*n&1) solve1();else solve0();}
}