思路：
二分讨论，网络流检验；
代码：
#include <bits/stdc++.h>
using namespace std;
#define INF 1e16
#define maxn 40005
#define ll long long
const ll dx[]={,-,,,};
const ll dy[]={,,,,-};
ll ai[][],id[][],suma,sumb,cnta,cntb,que[maxn],Max,ans;
ll deep[maxn],E[maxn],V[maxn],F[maxn],cnt,head[maxn],s,t,cntid;
ll n,m;
bool col[][];
inline void in(ll &now)
{
char Cget=getchar();now=;
while(Cget>''||Cget<'') Cget=getchar();
while(Cget>=''&&Cget<='')
{
now=now*+Cget-'';
Cget=getchar();
}
}
inline void edge_add(ll u,ll v,ll f)
{
E[++cnt]=head[u],V[cnt]=v,F[cnt]=f,head[u]=cnt;
E[++cnt]=head[v],V[cnt]=u,F[cnt]=,head[v]=cnt;
}
bool bfs()
{
for(ll i=s;i<=t;i++) deep[i]=-;
deep[s]=,que[]=s;ll h=,tail=,now;
while(h<tail)
{
now=que[h++];
for(ll i=head[now];i;i=E[i])
if(F[i]&&deep[V[i]]==-)
{
deep[V[i]]=deep[now]+;
if(V[i]==t) return true;
que[tail++]=V[i];
}
}
return false;
}
ll flowing(ll now,ll flow)
{
if(now==t||flow<=) return flow;
ll oldflow=,pos;
for(ll i=head[now];i;i=E[i])
{
if(!F[i]||deep[V[i]]!=deep[now]+) continue;
pos=flowing(V[i],min(flow,F[i]));
F[i]-=pos,F[i^]+=pos,oldflow+=pos,flow-=pos;
if(!flow) return oldflow;
}
if(!oldflow) deep[now]=-;
return oldflow;
}
bool check(ll x)
{
for(ll i=s;i<=t;i++) head[i]=;cnt=;
for(ll i=;i<=n;i++)
for(ll v=;v<=m;v++)
if(col[i][v])
{
edge_add(s,id[i][v],x-ai[i][v]);
for(ll e=;e<=;e++)
if(i+dx[e]>&&i+dx[e]<=n&&v+dy[e]>&&v+dy[e]<=m) edge_add(id[i][v],id[i+dx[e]][v+dy[e]],INF);
}
else edge_add(id[i][v],t,x-ai[i][v]);
ll res=;
while(bfs()) res+=flowing(s,INF);
return res==(x*cnta-suma);
}
int main()
{
freopen("data.txt","r",stdin);
ll T;in(T);
while(T--)
{
in(n),in(m),suma=,sumb=,cnta=,cntb=,cntid=,Max=;
for(ll i=;i<=n;i++)
for(ll v=;v<=m;v++)
{
in(ai[i][v]),col[i][v]=(i+v)%;
if(col[i][v]) suma+=ai[i][v],cnta++;
else sumb+=ai[i][v],cntb++;
id[i][v]=++cntid,Max=max(Max,ai[i][v]);
}
ans=-,s=,t=cntid+;
if(cnta!=cntb)
{
if((suma-sumb)%(cnta-cntb)==)
{
ll x=(suma-sumb)/(cnta-cntb);
if(x>=Max) if(check(x)) ans=x*cnta-suma;
}
}
else
{
if(suma==sumb)
{
ll l=Max,r=INF,mid;
while(l<=r)
{
mid=l+r>>;
if(check(mid)) r=mid-,ans=mid;
else l=mid+;
}
if(ans!=-) ans=ans*cnta-suma;
}
}
printf("%lld\n",ans);
}
return ;
}