7302 - 墓穴探险(tomb)

小向很喜欢玩单机游戏《古墓丽影》,他扮演一个考古学家劳拉在全球各个墓穴探险。其中一个游戏关卡是在一个法老王的墓地探险的过程中,有一个谜题,他试了一整天才解决这个谜题。

谜题是有一个n行m列的矩阵,每个格子都有一个数字,数字的数值在谜题的一开始都是0,在矩阵的每行每列都对应有一个可以旋转的按钮,左旋一次这个按钮就可以使得对应行或列矩阵内的所有数字减1,右旋一次则可以使得对应行或列的矩阵内的所有数字加1。

游戏关卡内另外有一些k条提示线索,每个线索要求i行j列的格子中最终的数字是x,对于没有提示的格子,那些都与谜题无关,可以不关心它的最终数字。

小向花了九牛二虎之力才解开这个谜题,于是他兴奋的向小李吹嘘自己的聪明才智。小李却不屑一顾,认为用最少的操作次数解开才是真正的高手。

于是小李把谜题抽象成若干组数据,需要小向用程序输出最少的左旋和右旋次数。不过小李也很懒,他设置的谜题数据是完全随机的,有时会出现无解的情况,那么对应输出字符串“No”即可。

输入

从文件tomb.in中读入数据。每个测试点包含多组测试数据。

输入的第一行是一个正整数t,表示测试数据的组数。

每组测试数据的第一行包含三个正整数n、m、k分别表示矩阵的行数、矩阵的列数、谜题的提示数。

接着k行,每行三个数字i、j、x,表示一组线索,要求最终i行j列的格子内的数字是x。

输出

输出到文件tomb.out中。每组测试数据输出1行,如果有解,则输出最少的操作次数,如果无解,输出“No”即可。

样例

输入

2
2 2 4
1 1 0
1 2 0
2 1 2
2 2 2
2 2 4
1 1 0
1 2 0
2 1 2
2 2 1

输出

2
No

提示

输入包含2组测试数据。

第一组测试数据谜题的目标如下:
00
22
操作2次第二行的按钮,每次加1,就可以满足题目条件。明显没有更优的方案。
第二组测试数据谜题的目标如下:
00
------------------------
21
每次操作之后,一定是两个格子的数字发生了加1或者减1,所以矩阵内所有数字之和一定是偶数,但是所有格子的目标和是奇数(0+0+2+1=3),所以必然无解。

来源

青少年编程挑战赛

时间限制 1 秒
内存限制 512 MB
讨论 统计
上一题 下一题