记录编号	612572	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[统一省选 2021]矩阵游戏	最终得分	100
用户昵称	终焉折枝	是否通过	通过
代码语言	C++	运行时间	5.154 s
提交时间	2026-02-24 14:39:28	内存使用	6.06 MiB

#include<iostream>
#include<vector>
#include<queue>
using namespace std;

const int MAXN = 1005;
const int INF = 1000000;
int T;
int n, m;
int b[MAXN][MAXN];
int a[MAXN][MAXN];
vector<pair<int, int> > g[MAXN];
bool vis[MAXN << 1];
int dis[MAXN << 1], in[MAXN << 1];
queue<int> q;

void init(){
    while(!q.empty()) q.pop();
    for(int i = 1;i <= n + m;i ++){
        dis[i] = 0;
        vis[i] = 1;
        in[i] = 0;
        q.push(i);
    }
}

void solve(){
    cin >> n >> m;
    for(int i = 1;i < n;i ++){
        for(int j = 1;j < m;j ++){
            cin >> b[i][j];
        }
    }
    for(int i = 1;i <= n;i ++)
        for(int j = 1;j <= m;j ++)
            a[i][j] = 0;
    for(int i = 2;i <= n;i ++){
        for(int j = 2;j <= m;j ++){
            a[i][j] = b[i - 1][j - 1] - a[i - 1][j] - a[i][j - 1] - a[i - 1][j - 1];
//            cout << a[i][j] << ' ';
        }
//        cout << endl;
    }
    for(int i = 1;i <= n + m + 1;i ++) g[i].clear(); 
    for(int i = 1;i <= n;i ++){
        for(int j = 1;j <= m;j ++){
            if((i + j) & 1){
                g[i].push_back(make_pair(j + n, a[i][j]));
                g[j + n].push_back(make_pair(i, INF - a[i][j]));
            }
            else{
                g[j + n].push_back(make_pair(i, a[i][j]));
                g[i].push_back(make_pair(j + n, INF - a[i][j]));
            } 
        }
    }
    init();
    while(!q.empty()){
        int u = q.front(); q.pop(); vis[u] = 0;
        for(auto x : g[u]){
            int v = x.first, w = x.second;
            if(dis[u] + w < dis[v]){
                dis[v] = dis[u] + w;
                if(!vis[v]){
                    in[v] ++;
                    if(in[v] > n + m + 1){
                        cout << "NO\n";
                        return;
                    }
                    vis[v] = 1;
                    q.push(v);
                }
            }
        }
    }
    bool flag = 1;
//    cout << "YES\n";
    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[j + n] - dis[i]);
            if(a[i][j] < 0) flag = 0;
//            cout << a[i][j] << ' ';
        }
//        cout << '\n';
    }
    if(flag){
        cout << "YES\n";
        for(int i = 1;i <= n;i ++){
            for(int j = 1;j <= m;j ++){
                cout << a[i][j] << ' ';
            }
            cout << '\n';
        }
    }
    else cout << "NO\n";
}

int main(){
    freopen("matrix.in", "r", stdin);
    freopen("matrix.out", "w", stdout);
    cin.tie(0) -> ios::sync_with_stdio(0);
    cin >> T;
    while(T --){
        solve();
    }
    return 0;
}