7302 - 墓穴探险(tomb)
时间限制 : 1 秒
内存限制 : 512 MB
小向很喜欢玩单机游戏《古墓丽影》,他扮演一个考古学家劳拉在全球各个墓穴探险。其中一个游戏关卡是在一个法老王的墓地探险的过程中,有一个谜题,他试了一整天才解决这个谜题。
谜题是有一个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组测试数据。
第一组测试数据谜题的目标如下:
| 0 | 0 |
|---|---|
| 2 | 2 |
| 操作2次第二行的按钮,每次加1,就可以满足题目条件。明显没有更优的方案。 | |
| 第二组测试数据谜题的目标如下: | |
| 0 | 0 |
| ------------ | ------------ |
| 2 | 1 |
| 每次操作之后,一定是两个格子的数字发生了加1或者减1,所以矩阵内所有数字之和一定是偶数,但是所有格子的目标和是奇数(0+0+2+1=3),所以必然无解。 |
来源
青少年编程挑战赛