310481: CF1840F. Railguns
Description
Tema is playing a very interesting computer game.
During the next mission, Tema's character found himself on an unfamiliar planet. Unlike Earth, this planet is flat and can be represented as an $n \times m$ rectangle.
Tema's character is located at the point with coordinates $(0, 0)$. In order to successfully complete the mission, he needs to reach the point with coordinates $(n, m)$ alive.
Let the character of the computer game be located at the coordinate $(i, j)$. Every second, starting from the first, Tema can:
- either use vertical hyperjump technology, after which his character will end up at coordinate $(i + 1, j)$ at the end of the second;
- or use horizontal hyperjump technology, after which his character will end up at coordinate $(i, j + 1)$ at the end of the second;
- or Tema can choose not to make a hyperjump, in which case his character will not move during this second;
The aliens that inhabit this planet are very dangerous and hostile. Therefore, they will shoot from their railguns $r$ times.
Each shot completely penetrates one coordinate vertically or horizontally. If the character is in the line of its impact at the time of the shot (at the end of the second), he dies.
Since Tema looked at the game's source code, he knows complete information about each shot — the time, the penetrated coordinate, and the direction of the shot.
What is the minimum time for the character to reach the desired point? If he is doomed to die and cannot reach the point with coordinates $(n, m)$, output $-1$.
InputThe first line of the input contains a single integer $T$ ($1 \le T \le 10^4$) — the number of test cases.
Then follow the descriptions of the test cases.
The first line of each test case contains two integers $n$ and $m$ ($1 \le n \cdot m \le 10^4$) — the size of the planet, its height and width.
The second line of each test case contains a single integer $r$ ($1 \le r \le 100$) — the number of shots.
Then follow $r$ lines, each describing one shot.
A shot is described by three integers $t$, $d$, $coord$. Where $t$ is the second at which the shot will be fired ($1 \le t \le 10^9$). $d$ is the direction of the shot ($d = 1$ denotes a horizontal shot, $d = 2$ denotes a vertical shot). $coord$ is the size of the penetrated coordinate ($0 \le coord \le n$ for $d = 1$, $0 \le coord \le m$ for $d = 2$).
The sum of the products $n \cdot m$ over all test cases does not exceed $10^4$.
OutputFor each test case, output a single number — the minimum time for the character to reach the coordinate $(n, m)$, or $-1$ if he is doomed to die.
ExampleInput5 1 3 4 1 2 0 2 2 1 3 2 2 4 1 1 3 3 6 2 1 0 2 1 1 2 1 2 2 2 0 2 2 1 2 2 2 2 1 3 7 1 2 2 1 1 7 2 1 2 2 5 9 1 2 3 2 0 5 1 2 4 2 2 7 1 0 4 6 7 6 1 2 12 1 3 4 1 0 17 2 3 1 2 6 16 2 6 3 2 4Output
5 -1 3 6 10Note
In the first test case, the character can move as follows: $(0, 0) \rightarrow (0, 1) \rightarrow (0, 2) \rightarrow (0, 3) \rightarrow (0, 3) \rightarrow (1, 3)$.
In the second test case, the character will not be able to leave the rectangle that will be completely penetrated by shots at the second $2$.
Input
题意翻译
Tema 在 $n·m$ 的网格内要从 $(0,0)$ 走到 $(n,m)$。第 $0$ 秒末 Tema 位于$(0,0)$。 假设 Tema 正位于 $(i,j)$，每秒他可以做三种行动： ①该秒末移动到 $(i+1,j)$； ②该秒末移动到 $(i,j+1)$； ③该秒末停留在 $(i,j)$。 机器人会发射 $r$ 次激光炮以阻挠他前进，具体为在第 $t$ 秒，向第 $x$ 行或第 $x$ 列发射激光炮，一整列或一整行都会受到炮击。若 Tema 在第 $t$ 秒末还停留在被炮击的单元格内则会被击毁。求 Tema 从 $(0,0)$ 到达 $(n,m)$ 的最短时间，若无法抵达，则输出 $-1$。 $r$ 次炮击格式为 $t,d,coord$ ，$t$ 表示炮击发生的时间，$d$ 表示炮击方式($d=1$ 时攻击一整行，$d=2$ 时攻击一整列)，$coord$ 表示攻击的是具体哪一行/列。Output
Tema正在玩一个有趣的电脑游戏。在他的下一个任务中，Tema的角色发现自己在了一个陌生的星球上。与地球不同，这个星球是平的，可以表示为一个n×m的矩形。Tema的角色位于坐标(0,0)的位置。为了成功完成他的任务，他需要活着到达坐标(n,m)的位置。
如果游戏角色位于坐标(i,j)，从第一秒开始，Tema可以选择以下操作之一：
1. 使用垂直超跳技术，这样他的角色在第二秒结束时将到达坐标(i+1,j)；
2. 使用水平超跳技术，这样他的角色在第二秒结束时将到达坐标(i,j+1)；
3. Tema也可以选择不进行超跳，在这种情况下，他的角色在这一秒内将不会移动。
居住在这个星球上的外星人是非常危险和敌对的。因此，他们会用轨道枪射击r次。每次射击完全穿透一个坐标的垂直或水平方向。如果角色在射击时正处于其冲击线上（在第二秒结束时），他将死亡。
由于Tema查看了游戏的源代码，他知道了关于每次射击的完整信息——射击的时间、穿透的坐标以及射击的方向。
问角色到达所需点(n,m)的最小时间是多少？如果他注定要死亡并且无法到达坐标(n,m)，输出-1。
输入输出数据格式：
输入：
- 第一行包含一个整数T（1≤T≤10^4）——测试用例的数量。
- 然后是T个测试用例的描述。
- 每个测试用例的第一行包含两个整数n和m（1≤n·m≤10^4）——星球的大小，即高度和宽度。
- 每个测试用例的第二行包含一个整数r（1≤r≤100）——射击次数。
- 然后是r行，每行描述一次射击。
- 射击由三个整数t、d、coord描述。其中t是射击发生的秒数（1≤t≤10^9），d是射击方向（d=1表示水平射击，d=2表示垂直射击），coord是被穿透的坐标的大小（0≤coord≤n对于d=1，0≤coord≤m对于d=2）。
- 所有测试用例的n·m乘积之和不超过10^4。
输出：
- 对于每个测试用例，输出一个数字——角色到达坐标(n,m)的最小时间，或者如果他将要死亡，则输出-1。
示例：
输入：
```
5
1 3
4
1 2 0
2 2 1
3 2 2
4 1 1
3 3
6
2 1 0
2 1 1
2 1 2
2 2 0
2 2 1
2 2 2
2 1
3
7 1 2
2 1 1
7 2 1
2 2
5
9 1 2
3 2 0
5 1 2
4 2 2
7 1 0
4 6
7
6 1 2
12 1 3
4 1 0
17 2 3
1 2 6
16 2 6
3 2 4
```
输出：
```
5
-1
3
6
10
```题目大意： Tema正在玩一个有趣的电脑游戏。在他的下一个任务中，Tema的角色发现自己在了一个陌生的星球上。与地球不同，这个星球是平的，可以表示为一个n×m的矩形。Tema的角色位于坐标(0,0)的位置。为了成功完成他的任务，他需要活着到达坐标(n,m)的位置。 如果游戏角色位于坐标(i,j)，从第一秒开始，Tema可以选择以下操作之一： 1. 使用垂直超跳技术，这样他的角色在第二秒结束时将到达坐标(i+1,j)； 2. 使用水平超跳技术，这样他的角色在第二秒结束时将到达坐标(i,j+1)； 3. Tema也可以选择不进行超跳，在这种情况下，他的角色在这一秒内将不会移动。 居住在这个星球上的外星人是非常危险和敌对的。因此，他们会用轨道枪射击r次。每次射击完全穿透一个坐标的垂直或水平方向。如果角色在射击时正处于其冲击线上（在第二秒结束时），他将死亡。 由于Tema查看了游戏的源代码，他知道了关于每次射击的完整信息——射击的时间、穿透的坐标以及射击的方向。 问角色到达所需点(n,m)的最小时间是多少？如果他注定要死亡并且无法到达坐标(n,m)，输出-1。 输入输出数据格式： 输入： - 第一行包含一个整数T（1≤T≤10^4）——测试用例的数量。 - 然后是T个测试用例的描述。 - 每个测试用例的第一行包含两个整数n和m（1≤n·m≤10^4）——星球的大小，即高度和宽度。 - 每个测试用例的第二行包含一个整数r（1≤r≤100）——射击次数。 - 然后是r行，每行描述一次射击。 - 射击由三个整数t、d、coord描述。其中t是射击发生的秒数（1≤t≤10^9），d是射击方向（d=1表示水平射击，d=2表示垂直射击），coord是被穿透的坐标的大小（0≤coord≤n对于d=1，0≤coord≤m对于d=2）。 - 所有测试用例的n·m乘积之和不超过10^4。 输出： - 对于每个测试用例，输出一个数字——角色到达坐标(n,m)的最小时间，或者如果他将要死亡，则输出-1。 示例： 输入： ``` 5 1 3 4 1 2 0 2 2 1 3 2 2 4 1 1 3 3 6 2 1 0 2 1 1 2 1 2 2 2 0 2 2 1 2 2 2 2 1 3 7 1 2 2 1 1 7 2 1 2 2 5 9 1 2 3 2 0 5 1 2 4 2 2 7 1 0 4 6 7 6 1 2 12 1 3 4 1 0 17 2 3 1 2 6 16 2 6 3 2 4 ``` 输出： ``` 5 -1 3 6 10 ```