CF1840F Railguns

Tema 正在玩一个非常有趣的电脑游戏。 在下一关任务中，Tema 的角色来到了一个陌生的星球。与地球不同，这个星球是平的，可以表示为一个 $n \times m$ 的矩形。 Tema 的角色位于坐标 $(0, 0)$。为了顺利完成任务，他需要活着到达坐标 $(n, m)$。 假设游戏角色当前位于坐标 $(i, j)$。从第一秒开始，每一秒，Tema 可以： - 使用垂直超跳技术，使角色在该秒结束时到达坐标 $(i + 1, j)$； - 或者使用水平超跳技术，使角色在该秒结束时到达坐标 $(i, j + 1)$； - 或者选择不进行超跳，此时角色在这一秒内不会移动。 这个星球上的外星人非常危险且充满敌意。因此，他们会用轨道炮射击 $r$ 次。 每次射击会完全贯穿某一条纵坐标或横坐标。如果角色在射击发生时（即在该秒结束时）正好处于被贯穿的坐标线上，他就会死亡。 由于 Tema 查看了游戏的源代码，他知道每次射击的全部信息——射击的时间、被贯穿的坐标以及射击的方向。 请问角色到达目标点 $(n, m)$ 的最短时间是多少？如果他注定无法到达 $(n, m)$，请输出 $-1$。

输入的第一行包含一个整数 $T$（$1 \le T \le 10^4$），表示测试用例的数量。 接下来是每个测试用例的描述。 每个测试用例的第一行包含两个整数 $n$ 和 $m$（$1 \le n \cdot m \le 10^4$），表示星球的高度和宽度。 每个测试用例的第二行包含一个整数 $r$（$1 \le r \le 100$），表示射击的次数。 接下来有 $r$ 行，每行描述一次射击。 每次射击由三个整数 $t$、$d$、$coord$ 描述。其中 $t$ 表示射击发生的时间（$1 \le t \le 10^9$），$d$ 表示射击的方向（$d = 1$ 表示横向射击，$d = 2$ 表示纵向射击），$coord$ 表示被贯穿的坐标（若 $d = 1$，则 $0 \le coord \le n$；若 $d = 2$，则 $0 \le coord \le m$）。 所有测试用例中 $n \cdot m$ 的总和不超过 $10^4$。

对于每个测试用例，输出一个整数，表示角色到达坐标 $(n, m)$ 的最短时间。如果他注定无法到达，则输出 $-1$。

在第一个测试用例中，角色可以按如下方式移动：$(0, 0) \rightarrow (0, 1) \rightarrow (0, 2) \rightarrow (0, 3) \rightarrow (0, 3) \rightarrow (1, 3)$。 在第二个测试用例中，角色无法离开在第 $2$ 秒被完全贯穿的矩形区域。 由 ChatGPT 4.1 翻译