← 返回题目列表

AtCoder · arc044_c

C. 梁

中文机器翻译题面 查看原题

問題文

高桥君, 生活在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