#2397. 矩阵游戏
矩阵游戏
矩阵游戏
题目描述
全国青少年信息学奥林匹克竞赛 Day1(A 卷)矩阵游戏(matrix) 矩阵游戏(matrix) 【题目描述】 Alice 有一个n × m 的矩阵ai,j(1 ≤i ≤n,1 ≤j ≤m),其每个元素为大小不超 过106 的非负整数。 Bob 根据该矩阵生成了一个(n−1)×(m−1) 的矩阵bi,j(1 ≤i ≤n−1,1 ≤j ≤m−1), 每个元素的生成公式为 bi,j = ai,j + ai,j+1 + ai+1,j + ai+1,j+1 现在Alice 忘记了矩阵ai,j,请你根据Bob 给出的矩阵bi,j 还原出ai,j。 【输入格式】 从文件matrix.in 中读入数据。 本题有多组数据。 第一行一个整数T 表示数据组数。 每组数据第一行两个正整数n, m,表示矩阵ai,j 的大小。 每组数据第2 ∼n 行每行m −1 个非负整数,表示bi,j。 【输出格式】 输出到文件matrix.out 中。 对于每组数据:
- 若矩阵bi,j 无法被生成,则输出一行一个字符串NO。
- 若矩阵bi,j 可被生成,则先输出一行一个字符串YES,接下来输出n 行每行m 个(用单个空格分隔的)大小不超过106 的非负整数表示ai,j。 若有多个矩阵ai,j 可生成给出的bi,j,输出其中任意一个即可。 【样例1 输入】 1 3 2 3 3 3 28 25 4 24 25 5 3 3 6 15 14 7 14 12 8 3 3 第4 页 共7 页
全国青少年信息学奥林匹克竞赛 Day1(A 卷)矩阵游戏(matrix) 9 0 3000005 10 0 0 【样例1 输出】 1 YES 2 7 8 8 3 8 5 4 4 4 7 9 5 YES 6 4 2 2 7 5 4 6 8 5 0 2 9 NO 【数据范围】 对于所有测试数据:1 ≤T ≤10,2 ≤n, m ≤300,0 ≤bi,j ≤4 × 106。 每个测试点的具体限制见下表: 测试点编号 n, m ≤ 特殊限制 1 ∼4 3 无 5 ∼7 10 m = 2 8 ∼10 100 11 ∼15 300 0 ≤bi,j ≤1 16 ∼20 无 第5 页 共7 页
输入格式
(见题面原文)
输出格式
(见题面原文)
数据范围
(见题面原文)
样例
样例 1
3
3 3
28 25
24 25
3 3
15 14
14 12
3 3
0 3000005
0 0
YES
7 8 8
8 5 4
4 7 9
YES
4 2 2
5 4 6
5 0 2
NO