AT_arc044_c [ARC044C] ビーム

[problemUrl]: https://atcoder.jp/contests/arc044/tasks/arc044_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 $を出力せよ。 出力の末尾に改行を入れること。(21:40修正)

### 部分点 この問題には部分点が設定されている。 - $ 1\ ≦\ W,H,Q\ ≦\ 100,\ T_i\ ≦\ 100(1\ ≦\ i\ ≦\ Q) $ を満たすデータセットに正解した場合は $ 30 $ 点が与えられる。 ### Sample Explanation 1 高橋君は以下の動きで、すべてのビームをよけることができます。 - はじめ、高橋君は$ (3,2) $にいる - 時刻$ 1.5 $に、$ (2,2) $に移動し、さらに$ (2,1) $に移動する - 時刻$ 2.5 $に、$ (1,1) $に移動する