問題文
高桥君, 生活在H × W网格上。左下角的方块是(1,1),右上角的方块是(W,H)。 然而,这个网格有点棘手,有时光束会飞向你。 作为人类,高桥希望尽可能避免被光束击中,因为一旦被光束击中,那就是“大问题”。
光束是 它以一对(時刻、方向、座標)的形式给出。时间是光束飞行的时间,方向是垂直或水平。
具体来说,光束(t,縦,a)是时间t所有满足1 ≦ i ≦ H的i反对大众(a,i)梁 通过(t,横,a)是时间t所有满足1 ≦ i ≦ W的i反对大众(i,a)。其他方格不会通过。
幸运的是,高桥君掌握了有关何时以及何种光束会飞行的所有信息。因此,我试图用最短的移动次数来躲避所有的光束。 高桥君将通过边缘彼此相邻的方块放置起来。 您可以移动1次。
由于高桥定期训练,因此他可以在单位时间内移动任意次数。 另外,高桥可以自由选择自己的初始位置,也可以在结束时处于任意方格。请注意,高桥不能走出网格。
求高桥的最小移动次数。如果高桥不可能在不被光束击中的情况下移动,那么 给出了-1。 由于它不满足
入力
输入将以以下形式通过标准输入给出。
W H Q T_1 D_1 X_1 . . . T_Q D_Q X_Q
- 1 行包含一个整数W,H,Q(1 ≦ W,H ≦ 10^5, 0 ≦ Q ≦10^5)。这些代表网格的水平长度、垂直长度以及光束飞行的次数。 光束信息在
- 2 第Q+1行中给出。其中i行中,T_i,D_i,X_i(1 ≦ T_i ≦10^5, 0 ≦ D_i ≦ 1, D_i=0のとき1 ≦ X_i ≦ W, D_i=1のとき1 ≦ X_i ≦ H)。 来自行D_i=0时发出光束(T_i,縦,X_i)是D_i=1时发出光束(T_i,横,X_i)代表飞行。另外,任何 对于i,j,(T_i,D_i,X_i) ≠ (T_j,D_j,X_j)很满意。
部分点
针对此问题设置了部分分数。 如果正确答案是满足
- 1 ≦ W,H,Q ≦ 100, T_i ≦ 100(1 ≦ i ≦ Q) 的数据集 30 分被给予。
出力
如果可以在不被光束击中一次的情况下移动,则输出高桥可以移动的最小次数。如果没有, 输出-1。
在输出末尾插入换行符。 (21:40 修正)入力例1
3 2 8 1 0 2 3 0 2 4 1 2 2 1 2 4 0 3 2 0 3 1 1 1 2 0 1
出力例1
3
高桥可以通过以下动作避开所有光束。
- 首先,高桥君 我在(3,2)转到
- 時刻1.5所有满足(2,2),然后 转到(2,1)移至
- 時刻2.5所有满足(1,1)移至
入力例2
2 4 10 3 1 1 2 1 3 3 0 1 2 1 4 1 1 3 2 1 2 3 1 2 1 0 1 3 1 4 2 0 2
出力例2
4
入力例3
3 3 5 1 0 3 1 0 2 1 1 3 1 1 2 1 0 1
出力例3
-1