G - Long Chess Board
問題文
縦$H$マス横$W$マスの長方形のチェス盤があります。
チェス盤の上から $i$ 番目、左から $j$ 番目のマスを $(i, j)$ と表記します。
最初、$(r_k, c_k)$にナイトが、$(r_b, c_b)$にビショップが置いてあります。
以下の操作を繰り返し$2$つのコマを同じマスに集めるために必要な操作回数の最小値を求めてください。ただし、操作の繰り返しにより$2$つのコマを同じマスに集めることができない場合には$-1$を出力してください。
-
どちらか$1$つのコマを選び、そのコマの動き方に従い$1$回動かす。
ここで、それぞれのコマは以下のように動かすことができます:- ナイト: 置いてあるマスを$(a, b)$とすると、以下のいずれかの条件を満たすマス$(c, d)~(1 \leq c \leq H, 1 \leq d \leq W)$に動かすことができます。
- $|a-c|=1$ かつ $|b-d|=2$
- $|a-c|=2$ かつ $|b-d|=1$
- ビショップ: 置いてあるマスを$(a, b)$とすると、以下の条件を満たすマス$(c, d)~(1 \leq c \leq H, 1 \leq d \leq W)$に動かすことができます。
- $|a-c|=|b-d|$
- ナイト: 置いてあるマスを$(a, b)$とすると、以下のいずれかの条件を満たすマス$(c, d)~(1 \leq c \leq H, 1 \leq d \leq W)$に動かすことができます。
$T$個のテストケースが与えられるので、それぞれについて答えを求めて下さい。
制約
- $1 \leq T \leq 10^4$
- $2 \leq H \leq 3$
- $H \leq W \leq 10^9$
- $1 \leq r_k, r_b \leq H$
- $1 \leq c_k, c_b \leq W$
- $(r_k, c_k) \ne (r_b, c_b)$
- 入力は全て整数である
- $1$つの入力の中に $H=2$ を満たすテストケースと $H=3$ を満たすテストケースが混在することはない。
部分点
以下の条件を満たすデータセットに正解したとき、記載された点数が与えられる。
- (20点) $H = 2$, ひとつの入力について、含まれる $W$の総和は$10^5$を超えない
- (20点) $H = 3$, ひとつの入力について、含まれる $W$の総和は$10^5$を超えない
- (30点) $H = 2$
- (30点) $H = 3$
追加の制約がないデータセットは存在しない。つまり、部分点1~4に正答すると満点の100点が与えられる。
入力
入力は以下の形式で標準入力から与えられる。
$T$
$case_1$
$\vdots$
$case_T$
各テストケースは以下の形式で与えられる。
$H$ $W$
$r_k$ $c_k$ $r_b$ $c_b$
出力
全体で $T$行出力せよ。
$i$行目には$i$個目のテストケースに対する答えを出力せよ。
2
2 4
1 1 1 4
2 71828
1 8 2 45905
2
22949
1つ目のテストケースについて、
- ナイトを$(2, 3)$に移動させる。
- ビショップを$(2, 3)$に移動させる。
とすることで、$2$回の操作で$2$つのコマを同じマスに集めることができます。
これ以上少ない操作で同じマスに集めることができないため、 $2$ を出力します。
このサンプルは部分点1の制約を満たします。
2
3 6
2 6 1 1
3 14159
2 65 3 5897
3
2916
1つ目のテストケースについて、
- ビショップを$(3, 3)$に移動させる。
- ビショップを$(1, 5)$に移動させる。
- ビショップを$(2, 6)$に移動させる。
とすることで、$3$回の操作で$2$つのコマを同じマスに集めることができます。
これ以上少ない操作で同じマスに集めることができないため、 $3$ を出力します。
このサンプルは部分点2の制約を満たします。
2
2 901234567
1 141592653 1 626433832
2 890123456
1 197169399 2 502881693
242420590
152856147
このサンプルは部分点3の制約を満たします。
2
3 987654321
1 159265358 2 323846264
3 876543210
3 209749445 1 781640628
82290453
285945592
このサンプルは部分点4の制約を満たします。