记录编号	612554	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[统一省选 2021]矩阵游戏	最终得分	100
用户昵称	HXF	是否通过	通过
代码语言	C++	运行时间	5.140 s
提交时间	2026-02-24 10:52:17	内存使用	6.76 MiB

#include<bits/stdc++.h>
#define int long long
#define fi first
#define se second
#define mp make_pair
using namespace std;
auto IOS = ios::sync_with_stdio(false);
auto CIN = cin.tie(nullptr);
int mread(){
    int x = 0, f = 1;
    char c = cin.get();
    while(c < '0' || c > '9'){
        if(c == '-'){
            f = -1;
        }
        c = cin.get();
    }
    while(c >= '0' && c <= '9'){
        x = x * 10 + c - '0';
        c = cin.get();
    }
    return x * f;
}
const int N = 305, M = N * N * 2;
int t = mread(), b[N][N], n, m, a[N][N];
int d[N + N], sum[N + N];
vector<pair<int, int> > v[N + N];
signed main(){
    while(t --){
        n = mread(), m = mread();
        for(int i = 1; i <= n + m; i ++){
            v[i].clear();
        }
        for(int i = 1; i < n; i ++){
            for(int j = 1; j < m; j ++){
                b[i][j] = mread();
            }
        }
        for(int i = 1; i <= n; i ++){
            a[i][m] = 0;
        }
        for(int i = 1; i <= m; i ++){
            a[n][i] = 0;
        }
        for(int i = n - 1; i >= 1; i --){
            for(int j = m - 1; j >= 1; j --){
                a[i][j] = b[i][j] - a[i + 1][j] - a[i][j + 1] - a[i + 1][j + 1];
            }
        }
        for(int i = 1; i <= n; i ++){
            for(int j = 1; j <= m; j ++){
                if(i + j & 1){
                    v[i].push_back(mp(n + j, a[i][j]));
                    v[n + j].push_back(mp(i, 1000000 - a[i][j]));
                }
                else{
                    v[n + j].push_back(mp(i, a[i][j]));
                    v[i].push_back(mp(n + j, 1000000 - a[i][j]));
                }
            }
        }
        memset(d, 0x3f, sizeof(d));
        memset(sum, 0, sizeof(sum));
        d[1] = 0;
        queue<int> q;
        q.push(1);
        bool e = true;
        while(q.size()){
            int x = q.front();
            q.pop();
            sum[x] ++;
            if(sum[x] == n + m + 3){
                e = false;
                break;
            }
            for(auto &t : v[x]){
                int y = t.fi, w = t.se;
                if(d[x] + w < d[y]){
                    d[y] = d[x] + w;
                    q.push(y);
                }
            }
        }
        if(e){
            cout << "YES\n";
            for(int i = 1; i <= n; i ++){
                for(int j = 1; j <= m; j ++){
                    int t = a[i][j];
                    if(i + j & 1){
                        t += d[i] - d[n + j];
                    }
                    else{
                        t += d[n + j] - d[i];
                    }
                    cout << t << " ";
                }
                cout << "\n";
            }
        }
        else{
            cout << "NO\n";
        }
    }
    return 0;
}