#P18368. Housing Estate
Housing Estate
Housing Estate
题目描述
ByteBud 公司计划建设一个住宅小区。公司已经购入一块矩形土地,并将它划分成 行、 列,共 个矩形格子。用 表示第 行、第 列的格子。
公司可以选择一些格子,在每个选中的格子上建造一栋住宅楼,也可以一栋都不建或在所有格子上建楼。你需要决定每个格子上的楼高,楼高用非负整数层数表示,0 表示不建楼。
规划规定,格子 上的楼高不能超过 。特别地,若 ,该格子不能建楼。
此外,公司已经确定了每个四格交点周围的总楼高。对于所有 、,给定整数 ,要求格子 、、、 上的楼高之和恰好等于 。
请判断是否存在满足全部要求的方案;如果存在,输出任意一种方案。
输入格式
第一行两个整数 ,表示行数和列数。
接下来 行,每行 个整数,第 行第 个数为 。
接下来 行,每行 个整数,第 行第 个数为 。
输出格式
如果不存在方案,只输出一行 NIE。
如果存在方案,第一行输出 TAK,接下来输出 行,每行 个非负整数 ,表示各格子上的楼高。它们必须满足
以及对所有 、,
TAK 和 NIE 中的每个字母都可以使用大写或小写。如果有多种方案,可以输出任意一种。
数据范围
- 。
- 。
- 。
- 每个输入文件只有一组数据。
样例输入 1
3 4
5 7 9 4
3 4 9 6
9 0 8 5
11 26 20
13 16 18
样例输出 1
TAK
0 6 9 3
1 4 7 1
8 0 5 5
样例输入 2
2 2
0 0
0 0
1000
样例输出 2
NIE
样例说明
第一组样例给出一种合法楼高方案。第二组样例的四个格子都不能建楼,楼高总和只能为 0,不能达到要求的 1000,因此无解。