考虑没有「其每个元素为大小不超过 \({10}^6\) 的非负整数」这个限制怎么做，显然令 \(a_{i,1}=a_{1,j}\;(1\le i\le n,\;1\le j\le m)\) 然后一个一个算其余的 \(a_{i,j}\) 即可。
\[\left[\begin{matrix}a_{1,1} & a_{1,2} & a_{1,3} & a_{1,4}\\ a_{2,1} & a_{2,2} & a_{2,3} & a_{2,4}\\ a_{3,1} & a_{3,2} & a_{3,3} & a_{3,4}\\ a_{4,1} & a_{4,2} & a_{4,3} & a_{4,4}\end{matrix}\right] \]我们得到了一个弱化版的答案，现在加上这个条件。考虑这个矩阵的第 \(i\) 行，若 \(j\) 为奇数加一个 \(r_i\)，反之减一个 \(r_i\)，列类似：
\[\left[\begin{matrix}a_{1,1}+r_1+c_1 & a_{1,2}-r_1+c_2 & a_{1,3}+r_1+c_3 & a_{1,4}-r_1+c_4\\ a_{2,1}+r_2-c_1 & a_{2,2}-r_2-c_2 & a_{2,3}+r_2-c_3 & a_{2,4}-r_2-c_4\\ a_{3,1}+r_3+c_1 & a_{3,2}-r_3+c_2 & a_{3,3}+r_3+c_3 & a_{3,4}-r_3+c_4\\ a_{4,1}+r_4-c_1 & a_{4,2}-r_4-c_2 & a_{4,3}+r_4-c_3 & a_{4,4}-r_4-c_4\end{matrix}\right] \]这样表示仍然是满足题意的。非常像差分约束，但是加法我们不会做，于是定义：
\[r_i'=\begin{cases}r_i, &i\equiv 1\pmod 2\\ -r_i & i\equiv 0\pmod 2\end{cases}\\ c_i'=\begin{cases}c_i, &i\equiv 0\pmod 2\\ -c_i & i\equiv 1\pmod 2\end{cases} \]原矩阵变成了：
\[\left[\begin{matrix}a_{1,1}+r_1'-c_1' & a_{1,2}-r_1'+c_2' & a_{1,3}+r_1'-c_3' & a_{1,4}-r_1'+c_4'\\ a_{2,1}-r_2'+c_1' & a_{2,2}+r_2'-c_2' & a_{2,3}-r_2'+c_3' & a_{2,4}+r_2'-c_4'\\ a_{3,1}+r_3'-c_1' & a_{3,2}-r_3'+c_2' & a_{3,3}+r_3'-c_3' & a_{3,4}-r_3'+c_4'\\ a_{4,1}-r_4'+c_1' & a_{4,2}+r_4'-c_2' & a_{4,3}-r_4'+c_3' & a_{4,4}+r_4'-c_4'\end{matrix}\right] \]就可以差分约束了。
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e6+10,M=2e6+10;
int head[N],ver[M],nxt[M],tot=0,edge[M];
void add(int x,int y,int z)
{
ver[++tot]=y;
edge[tot]=z;
nxt[tot]=head[x];
head[x]=tot;
}
int dis[N],cnt[N];int n,m;
bool vis[N],book[N];
bool spfa(int S)
{
queue<int> que;
dis[S]=0;
que.push(S);
while(!que.empty())
{
int x=que.front();que.pop();
book[x]=1;
vis[x]=0;
for(int i=head[x];i;i=nxt[i])
{
int y=ver[i],z=edge[i];
if(dis[x]+z>dis[y])
{
dis[y]=dis[x]+z;
if(++cnt[y]>n+m)return true;
if(!vis[y])
{
vis[y]=1;
que.push(y);
}
}
}
}
return false;
}
int a[310][310],b[310][310];
void sol()
{
memset(vis,0,sizeof(vis));
memset(dis,-0x3f,sizeof(dis));
memset(book,0,sizeof(book));
memset(cnt,0,sizeof(cnt));
memset(a,0,sizeof(a));
scanf("%lld%lld",&n,&m);
for(int i=1;i<n;i++)for(int j=1;j<m;j++)scanf("%lld",&b[i][j]);
for(int i=2;i<=n;i++)for(int j=2;j<=m;j++)a[i][j]=b[i-1][j-1]-a[i][j-1]-a[i-1][j]-a[i-1][j-1];
memset(head,0,sizeof(head));tot=0;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
if((i+j)&1)add(i,j+n,-a[i][j]),add(j+n,i,a[i][j]-1e6);
else add(j+n,i,-a[i][j]),add(i,j+n,a[i][j]-1e6);
}
}
if(spfa(1)){puts("NO");return;}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
if((i+j)&1)a[i][j]+=-dis[i]+dis[j+n];
else a[i][j]+=dis[i]-dis[j+n];
}
}
puts("YES");
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)printf("%lld ",a[i][j]);
puts("");
}
}
signed main()
{
// freopen("matrix5.in","r",stdin);
int T;
scanf("%lld",&T);
while(T--) sol();
return 0;
}