A7346 | 墓穴探险（tomb）
时间限制1s
内存限制512MB
通过 / 提交0/0
题目描述
小向很喜欢玩单机游戏《古墓丽影》，他扮演一个考古学家劳拉在全球各个墓穴探险。其中一个游戏关卡是在一个法老王的墓地探险的过程中，有一个谜题，他试了一整天才解决这个谜题。
谜题是有一个 $n$ 行 $m$ 列的矩阵，每个格子都有一个数字，数字的数值在谜题的一开始都是 $0$，在矩阵的每行每列都对应有一个可以旋转的按钮，左旋一次这个按钮就可以使得对应行或列矩阵内的所有数字减 $1$，右旋一次则可以使得对应行或列的矩阵内的所有数字加 $1$。
游戏关卡内另外有一些 $k$ 条提示线索，每个线索要求 $i$ 行 $j$ 列的格子中最终的数字是 $x$，对于没有提示的格子，那些都与谜题无关，可以不关心它的最终数字。
小向花了九牛二虎之力才解开这个谜题，于是他兴奋的向小李吹嘘自己的聪明才智。小李却不屑一顾，认为用最少的操作次数解开才是真正的高手。
于是小李把谜题抽象成若干组数据，需要小向用程序输出最少的左旋/右旋次数。不过小李也很懒，他设置的谜题数据是完全随机的，有时会出现无解的情况，那么对应输出字符串 "
谜题是有一个 $n$ 行 $m$ 列的矩阵，每个格子都有一个数字，数字的数值在谜题的一开始都是 $0$，在矩阵的每行每列都对应有一个可以旋转的按钮，左旋一次这个按钮就可以使得对应行或列矩阵内的所有数字减 $1$，右旋一次则可以使得对应行或列的矩阵内的所有数字加 $1$。
游戏关卡内另外有一些 $k$ 条提示线索，每个线索要求 $i$ 行 $j$ 列的格子中最终的数字是 $x$，对于没有提示的格子，那些都与谜题无关，可以不关心它的最终数字。
小向花了九牛二虎之力才解开这个谜题，于是他兴奋的向小李吹嘘自己的聪明才智。小李却不屑一顾，认为用最少的操作次数解开才是真正的高手。
于是小李把谜题抽象成若干组数据，需要小向用程序输出最少的左旋/右旋次数。不过小李也很懒，他设置的谜题数据是完全随机的，有时会出现无解的情况，那么对应输出字符串 "
No" 即可。输入格式
每个测试点包含多组测试数据。
输入的第一行是一个正整数 $t$，表示测试数据的组数。
每组测试数据的第一行包含三个正整数 $n,m,k$ 分别表示矩阵的行数、矩阵的列数、谜题的提示数。
接着 $k$ 行，每行三个数字 $i,j,x$，表示一组线索，要求最终 $i$ 行 $j$ 列的格子内的数字是 $x$。
输入的第一行是一个正整数 $t$，表示测试数据的组数。
每组测试数据的第一行包含三个正整数 $n,m,k$ 分别表示矩阵的行数、矩阵的列数、谜题的提示数。
接着 $k$ 行，每行三个数字 $i,j,x$，表示一组线索，要求最终 $i$ 行 $j$ 列的格子内的数字是 $x$。
输出格式
每组测试数据输出 $1$ 行，如果有解，则输出最少的操作次数，如果无解，输出
"No" 即可。输入输出样例
输入 #1
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
输出 #1
2 No
### 样例 1 解释
输入包含 $2$ 组测试数据。
第一组测试数据谜题的目标如下：
```text
0 0
2 2
```
操作 $2$ 次第二行的按钮，每次加 $1$，就可以满足题目条件。明显没有更优的方案。
第二组测试数据谜题的目标如下：
```text
0 0
2 1
```
每次操作之后，一定是两个格子的数字发生了加 $1$ 或者减 $1$，所以矩阵内所有数字之和一定是偶数，但是目标的所有格子的之和是奇数（$0+0+2+1=3$），所以必然无解。
### 附件
更多样例请查看：[tomb test.zip](https://pms-wscdn.xmwol.com/file/23672222ff7456d5.zip)
### 数据范围
对于所有测试数据有：
$$ 1 \le t \le 5 $$
$$ 1 \le n,m \le 1000 $$
$$ 1 \le k \le n \times m $$
$$ 1 \le i \le n $$
$$ 1 \le j \le m $$
$$ |x| \le 10^5 $$
保证两两不同的线索之间的网格均不同。
保证每个测试点的 $k$ 之和不会超过 $2 \times 10^6$。
| 测试点 | $n,m \le$ | 特殊性质 |
| ----- | --------- | ----- |
| 1~3 | 10 | 无 |
| 4 | 10 | $x=1$ |
| 5~7 | 50 | 无 |
| 8 | 50 | $n=1$ |
| 9~12 | 100 | 无 |
| 13 | 100 | $k=1$ |
| 14 | 500 | $n=1$ |
| 15~16 | 500 | $x=i$ |
| 17~20 | 1000 | 无 |
输入包含 $2$ 组测试数据。
第一组测试数据谜题的目标如下：
```text
0 0
2 2
```
操作 $2$ 次第二行的按钮，每次加 $1$，就可以满足题目条件。明显没有更优的方案。
第二组测试数据谜题的目标如下：
```text
0 0
2 1
```
每次操作之后，一定是两个格子的数字发生了加 $1$ 或者减 $1$，所以矩阵内所有数字之和一定是偶数，但是目标的所有格子的之和是奇数（$0+0+2+1=3$），所以必然无解。
### 附件
更多样例请查看：[tomb test.zip](https://pms-wscdn.xmwol.com/file/23672222ff7456d5.zip)
### 数据范围
对于所有测试数据有：
$$ 1 \le t \le 5 $$
$$ 1 \le n,m \le 1000 $$
$$ 1 \le k \le n \times m $$
$$ 1 \le i \le n $$
$$ 1 \le j \le m $$
$$ |x| \le 10^5 $$
保证两两不同的线索之间的网格均不同。
保证每个测试点的 $k$ 之和不会超过 $2 \times 10^6$。
| 测试点 | $n,m \le$ | 特殊性质 |
| ----- | --------- | ----- |
| 1~3 | 10 | 无 |
| 4 | 10 | $x=1$ |
| 5~7 | 50 | 无 |
| 8 | 50 | $n=1$ |
| 9~12 | 100 | 无 |
| 13 | 100 | $k=1$ |
| 14 | 500 | $n=1$ |
| 15~16 | 500 | $x=i$ |
| 17~20 | 1000 | 无 |
C++ 编辑器
输入
输出
可保存默认模板；新题优先使用已保存模板。
当前快捷键仅展示，暂不支持修改。
- 撤销
Ctrl / ⌘ + Z - 重做
Ctrl / ⌘ + Y - 查找
Ctrl / ⌘ + F - 全选
Ctrl / ⌘ + A - 复制
Ctrl / ⌘ + C - 剪切
Ctrl / ⌘ + X - 粘贴
Ctrl / ⌘ + V - 自动排版
工具栏排版按钮 - 草稿保存
编辑时自动保存到本机
历史
提交记录
状态说明时间源码
AI
作答助手
你好，我是作答助手。可以问思路、复杂度、样例含义或代码报错原因；不会直接给出完整 AC 代码。
确定要清空代码吗？