记录编号	612915	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	3580.[统一省选 2021]矩阵游戏	最终得分	100
用户昵称	xuyuqing	是否通过	通过
代码语言	C++	运行时间	4.937 s
提交时间	2026-02-27 09:14:56	内存使用	6.33 MiB

#include <cstdio>
#include <cstring>
#include <iostream>
#include <queue>
#include <string>
#include <utility>
#include <vector>

using namespace std;

class fastIn {
	private:
	
	char buf [1 << 20];
	char *p1 = buf;
	char *p2 = buf;
	
	inline char getch ();
	
	public:
	
	template <typename NumT>
	void read (NumT &num);
	
	template <typename NumT>
	fastIn& operator >> (NumT &num);
};

inline char fastIn::getch () {
	if (p1 == p2) {
		p1 = buf;
		p2 = buf + fread (buf, 1, 1 << 20, stdin);
		if (p1 == p2) {
			return EOF;
		}
	}
	return *p1++;
}

template <typename NumT>
void fastIn::read (NumT &num) {
	char ch = getch ();
	NumT op = 1;
	num = 0;
	
	while (ch < '0' || '9' < ch) {
		op = ((ch == '-') ? -1 : 1);
		ch = getch ();
	}
	while ('0' <= ch && ch <= '9') {
		num *= 10;
		num += (ch - '0');
		ch = getch ();
	}
	
	num *= op;
}

template <typename NumT>
fastIn& fastIn::operator >> (NumT &num) {
	read (num);
	return *this;
}

fastIn fin;

const int N = 322 << 1;
const int INF = 1e6;

int t;
int n;
int m;
int a[N][N];
int b[N][N];
vector<pair<int, int>> graph[N];
int dis[N];
int vis[N];
int cc[N];

int main () {

    freopen ("matrix.in", "r", stdin);
    freopen ("matrix.out", "w", stdout);
    
    fin >> t;
    for (int index = 1; index <= t; index++) {
        memset (cc, 0, sizeof (cc));
        fin >> n >> m;
        for (int i = 1; i < n; i++) {
            for (int j = 1; j < m; j++) {
                fin >> b[i][j];
            }
        }

        for (int i = 1; i <= n; i++) {
            a[i][1] = 0;
        }
        for (int i = 1; i <= m; i++) {
            a[1][i] = 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 - 1] - a[i - 1][j] - a[i][j - 1];
            }
        }

        // for (int i = 1; i <= n; i++) {
        //     for (int j = 1; j <= m; j++) {
        //         cout << a[i][j] << ' ';
        //     }
        //     cout << endl;
        // }

        for (int i = 1; i <= n + m + 1; i++) {
            graph[i].clear();
        }
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                if ((i + j) & 1) {
                    graph[i].emplace_back(j + n, a[i][j]);
                    graph[j + n].emplace_back(i, INF - a[i][j]);
                }
                else {
                    graph[j + n].emplace_back(i, a[i][j]);
                    graph[i].emplace_back(j + n, INF - a[i][j]);
                }
            }
        }

        bool flag = false;
        queue<int> q;
        for (int i = 1; i <= n + m; i++) {
            dis[i] = 0;
            vis[i] = true;
            cc[i] = 0;
            q.push(i);
        }
        while (!q.empty()) {
            int u = q.front();
            q.pop();
            vis[u] = false;
            for (auto [v, w] : graph[u]) {
                if (dis[u] + w < dis[v]) {
                    dis[v] = dis[u] + w;
                    if (!vis[v]) {
                        cc[v]++;
                        if (cc[v] > n + m + 1) {
                        // cout << "NO" << endl;
                        printf ("NO\n");
                            goto end;
                        }
                        vis[v] = true;
                        q.push(v);
                    }
                }
            }
        }

        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]);    
                }
                if (a[i][j] < 0) {
                    // cout << "NO" << endl;
                    printf ("NO\n");
                    goto end;
                }
            }
        }

        // cout << "YES" << endl;
        printf ("YES\n");

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                // cout << a[i][j] << ' ';
                printf ("%d ", a[i][j]);
            }
            // cout << endl;
            printf ("\n");
        }

        end:

        continue;
    }

    return 0;
}