A5956. 「联合省选 2021 A」矩阵游戏
编程题
省选/NOI-
知识点
题目描述
Alice 有一个 $n \times m$ 的矩阵 $a_{i, j}$（$1 \le i \le n$，$1 \le j \le m$），其每个元素为大小不超过 ${10}^6$ 的非负整数。
Bob 根据该矩阵生成了一个 $(n - 1) \times (m - 1)$ 的矩阵 $b_{i, j}$（$1 \le i \le n - 1$，$1 \le j \le m - 1$），每个元素的生成公式为
$$ b_{i, j} = a_{i, j} + a_{i, j + 1} + a_{i + 1, j} + a_{i + 1, j + 1} $$
现在 Alice 忘记了矩阵 $a_{i, j}$，请你根据 Bob 给出的矩阵 $b_{i, j}$ 还原出 $a_{i, j}$。
Bob 根据该矩阵生成了一个 $(n - 1) \times (m - 1)$ 的矩阵 $b_{i, j}$（$1 \le i \le n - 1$，$1 \le j \le m - 1$），每个元素的生成公式为
$$ b_{i, j} = a_{i, j} + a_{i, j + 1} + a_{i + 1, j} + a_{i + 1, j + 1} $$
现在 Alice 忘记了矩阵 $a_{i, j}$，请你根据 Bob 给出的矩阵 $b_{i, j}$ 还原出 $a_{i, j}$。
输入格式
**本题有多组数据。**
第一行，一个整数 $T$，表示数据组数。对于每组数据：
第一行，两个正整数 $n, m$，表示矩阵 $a_{i, j}$ 的大小。
接下来 $n - 1$ 行，每行 $m - 1$ 个非负整数，表示 $b_{i, j}$。
第一行，一个整数 $T$，表示数据组数。对于每组数据：
第一行，两个正整数 $n, m$，表示矩阵 $a_{i, j}$ 的大小。
接下来 $n - 1$ 行，每行 $m - 1$ 个非负整数，表示 $b_{i, j}$。
输出格式
对于每组数据：
1. 若矩阵 $b_{i, j}$ 无法被生成，则输出一行一个字符串
2. 若矩阵 $b_{i, j}$ 可被生成，则先输出一行一个字符串
若有多个矩阵 $a_{i, j}$ 可生成给出的 $b_{i, j}$，输出其中任意一个即可。
1. 若矩阵 $b_{i, j}$ 无法被生成，则输出一行一个字符串
NO。2. 若矩阵 $b_{i, j}$ 可被生成，则先输出一行一个字符串
YES，接下来输出 $n$ 行每行 $m$ 个（用单个空格分隔的）大小不超过 ${10}^6$ 的非负整数表示 $a_{i, j}$。若有多个矩阵 $a_{i, j}$ 可生成给出的 $b_{i, j}$，输出其中任意一个即可。
输入输出样例
输入 #1
3 3 3 28 25 24 25 3 3 15 14 14 12 3 3 0 3000005 0 0
输出 #1
YES 7 8 8 8 5 4 4 7 9 YES 4 2 2 5 4 6 5 0 2 NO
说明/提示
对于所有测试数据：$1 \le T \le 10$，$2 \le n, m \le 300$，$0 \le b_{i, j} \le 4 \times {10}^6$。
每个测试点的具体限制见下表：
| 测试点编号 | $n, m \le$ | 特殊限制 |
|:-:|:-:|:-:|
| $1 \sim 4$ | $3$ | 无 |
| $5 \sim 7$ | $10$ | $m = 2$ |
| $8 \sim 10$ | $100$ | $m = 2$ |
| $11 \sim 15$ | $300$ | $0 \le b_{i, j} \le 1$ |
| $16 \sim 20$ | $300$ | 无 |
每个测试点的具体限制见下表：
| 测试点编号 | $n, m \le$ | 特殊限制 |
|:-:|:-:|:-:|
| $1 \sim 4$ | $3$ | 无 |
| $5 \sim 7$ | $10$ | $m = 2$ |
| $8 \sim 10$ | $100$ | $m = 2$ |
| $11 \sim 15$ | $300$ | $0 \le b_{i, j} \le 1$ |
| $16 \sim 20$ | $300$ | 无 |