C - ビーム Editorial /

Time Limit: 2 sec / Memory Limit: 256 MB

問題文

高橋君は、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