大意
给你一个矩阵 \(b\)，求还原经过一次变换的矩阵 \(a\)。一次变换是把一个点的值变成以它为左上的 \(2\times 2\) 的小矩阵内的元素和。
Sol
好强的差分约束题！
首先考虑随意构造出一组解。然后考虑调整这个解使得满足范围。
构造解非常轻松，你只要把 \(a\) 中最后一行和最后一列全部变成 \(0\)，然后就从下往上依次填就可以了。
然后考虑数据范围的约束。考虑这样一个结论，就是说，你如果对某一行或者列进行交替的减一个数或者加一个数是合法的。这样的话，你可以形成以下这样的矩阵：
\[\begin{bmatrix}a_{1,1}+r_{1}+c_{1}&a_{1,2}-r_{1}+c_{2}&\cdots&a_{1,m}+r_{1}+c_{m}\\a_{2,1}+r_{2}-c_{1}&a_{2,2}-r_{2}-c_{2}&\cdots&a_{2,m}+r_{2}-c_{m}\\\vdots&\vdots&\ddots&\vdots\\a_{n,1}+r_{n}+c_{1}&a_{n,2}-r_{n}+c_{2}&\cdots&a_{n,m}+r_{n}+c_{m}\end{bmatrix}
\]
这样我们形成以下若干约束：
\[0\le a_{i,j}+(-1)^{j+1}r_i+(-1)^{i+1}c_j\le 10^6
\]
不难发现如果一正一负是已经满足了差分约束的需求的。但是可能会同正或者同负，这个时候发扬人类智慧，换一种方式，就是你对于每个位置，当 \(i,j\) 奇偶性相同的时候，\(c\) 负 \(r\) 正，反之就 \(c\) 正 \(r\) 负，这样保证了正负不同，并且还是满足正负交替，也就是不影响正确性。具体地，就是变成下面这个样子：
\[\begin{bmatrix}a_{1,1}+r_{1}-c_{1}&a_{1,2}-r_{1}+c_{2}&\cdots&a_{1,m}+r_{1}-c_{m}\\a_{2,1}-r_{2}+c_{1}&a_{2,2}+r_{2}-c_{2}&\cdots&a_{2,m}-r_{2}+c_{m}\\\vdots&\vdots&\ddots&\vdots\\a_{n,1}+r_{n}-c_{1}&a_{n,2}-r_{n}+c_{2}&\cdots&a_{n,m}+r_{n}-c_{m}\end{bmatrix}
\]
然后跑一遍差分约束求答案就可以了。
Code
// Problem: P7515 [省选联考 2021 A 卷] 矩阵游戏
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P7515
// Memory Limit: 512 MB
// Time Limit: 1000 ms
// Time: 2022-04-16 11:56:03
#include<bits/stdc++.h>
#define int long long
#define inf (1<<30)
#define INF (1ll<<60)
#define pb emplace_back
#define pii pair<int,int>
#define mkp make_pair
#define fi first
#define se second
#define rep(i,j,k) for(int i=(j);i<=(k);i++)
#define per(i,j,k) for(int i=(j);i>=(k);i--)
#define pt(a) cerr<<#a<<'='<<a<<' '
#define pts(a) cerr<<#a<<'='<<a<<'\n'
using namespace std;
const int MV=1e6;
const int MAXN=310;
struct node{
int x,w,cnt;node(){}
node(int _x,int _w,int _cnt){x=_x;w=_w;cnt=_cnt;}
bool friend operator<(node a,node b){return a.w>b.w;}
};
struct Edge{int to,w;};
int b[MAXN][MAXN],a[MAXN][MAXN];
priority_queue<node> q;
vector<Edge> e[MAXN<<1];
int dis[MAXN<<1];
void solve(){
int n,m;cin>>n>>m;
rep(i,1,n-1) rep(j,1,m-1) cin>>b[i][j];
memset(a,0,sizeof(a));
per(i,n-1,1) per(j,m-1,1) a[i][j]=b[i][j]-a[i+1][j]-a[i][j+1]-a[i+1][j+1];
rep(i,1,n) rep(j,1,m){
if(i%2==j%2) e[i].pb(Edge{j+n,a[i][j]}),e[j+n].pb(Edge{i,MV-a[i][j]});
else e[j+n].pb(Edge{i,a[i][j]}),e[i].pb(Edge{j+n,MV-a[i][j]});
}rep(i,1,n+m) e[0].pb(Edge{i,0});
memset(dis,0x3f,sizeof(dis));dis[0]=0;
q.push(node(0,0,-1));
bool negcir=0;
while(!q.empty()){
node now=q.top();q.pop();
if(dis[now.x]<now.w) continue;
if(now.cnt>n+m){negcir=1;break;}
for(auto s:e[now.x]){
node nxt=node(s.to,now.w+s.w,now.cnt+1);
if(dis[nxt.x]>nxt.w){
dis[nxt.x]=nxt.w;
q.push(nxt);
}
}
}
if(negcir){
cout<<"NO\n";
}else{
cout<<"YES\n";
rep(i,1,n){
rep(j,1,m){
if(i%2==j%2) cout<<a[i][j]+dis[i]-dis[j+n]<<' ';
else cout<<a[i][j]-dis[i]+dis[j+n]<<' ';
}cout<<'\n';
}
}while(!q.empty()) q.pop();
rep(i,1,n+m) e[i].clear();
}
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
int T;for(cin>>T;T--;) solve();
return 0;
}