European Girls'
Olympiad in Informatics
EGOI - 2022

SuperpieceDay2 Tasks
Japanese (JPN)

Antalya / Türkiye

スーパー駒 (Superpiece)
問題名

スーパー駒

入力ファイル

標準入力

出力ファイル

標準出力

実行時間制限

1秒

メモリ制限

256MB

あなたは無限に広いチェス盤を与えられた．この問題では，チェス盤は無限の二次元のマス目であり，各マスは (r, c) で表される．ここで，r は行を表し，c は列を示すものとする．
現在チェス盤に存在する唯一の駒は superpiece である．superpiece の有効な動きのリストは，文字列"QRBNKP" からいくつかの文字を取り出した，空でない文字列として与えられる．各ターンでは，superpiece は与えられたチェスの駒のひとつとして動くことができる．
superpiece は最初，マス (a, b) に配置されている． このとき，指定されたマス (c, d) に到達するために必要な移動回数の最小値を計算せよ．
この問題において適用されるチェスのルールを以下に示す．
駒はクイーン，ルーク，ビショップ，ナイト，キング，ポーンの 6 種類である．これらの駒は，次のような動きをする：
クイーン（'Q' で示される）は，現在いるマスと同じ行，列，または対角線内の任意のマスに移動できる．正確には, k ≠ 0 となる任意の整数に対して ，クイーンが (a, b) にいるとき，(a, b + k)または (a + k, b) , (a + k, b + k) ，(a + k, b − k) へ移動できる．

ルーク（'R' で示される）は，現在いるマスと同じ行または同じ列のマスに移動できる．正確には，k ≠ 0 となる任意の整数に対して，ルークが (a, b) にいるとき， (a + k, b) または (a, b + k)へ移動できる．

Superpiece (1 of 5)

ビショップ（'B' で示される）は，現在いるマスと同じ対角線内の任意のマスに移動できる．正確には，k ≠ 0 となる任意の整数に対して，ビショップが (a, b) にいるとき，(a + k, b + k) または(a + k, b − k) へ移動できる．

ナイト（'N' で示される）は，アルファベット「L」の形に移動することができる．まず，いずれかの方向に 2 つのマスを移動し，次に直交する方向に1 つのマスを移動できる．正確には，k ≠ 0と な る 任 意 の 整 数 に 対 し て ， ナ イ ト が (a, b) に い る と き ， (a + 1, b + 2) ， (a + 1, b − 2) ，(a + 2, b + 1)， (a + 2, b − 1) ， (a − 2, b + 1) ， (a − 2, b − 1) ， (a − 1, b + 2) ， (a − 1, b − 2)のいずれかに移動できる．

キング（'K' で示される）は，現在のマスに直接隣接する 8 つのマスのいずれかに移動できる．正
確 に は ， キ ン グ が (a, b) に い る と き (a, b + 1) ， (a, b − 1) ， (a + 1, b) ， (a − 1, b) ，(a + 1, b + 1)，(a + 1, b − 1)，(a − 1, b + 1)，(a − 1, b − 1) のいずれかに移動できる．

ポーン（'P' で示される）は，ちょうど 1 マス前方に移動できる．正確には，ポーンが (a, b) にいるとき，(a + 1, b) へ移動できる．

上記以外で，チェスに関して知っているルールや動きは本問題に適用できないので，上記に挙げられたもののみ使用すること．

Superpiece (2 of 5)

また，英語では，チェスの駒を表記する際，よく名前の最初の文字を使用するが，kNight については 2番目の文字を使用することに注意すること．（King との混同を避けるためである）

入力
1 行目には，プログラムが処理すべきクエリの数 q が書かれている．次の行からの各 2 行には，クエリの情報が以下のように書かれている．
クエリの最初の行には，superpiece がチェスのどの駒の動きを取ることができるかを指定する，空でない文字列が書かれている．この文字列は大文字の文字列 "QRBNKP" の部分集合を含み，含まれる文字は 同じ順序 で表示される．つまり，"QRBNKP" の部分列となる．
クエリの 2 行目には，元々のマスおよび移動先のマスを表す 4 つの整数 a, b, c, d が書かれている．なお，(a, b) ≠ (c, d) であること，すなわち元々のマスと移動先のマスが異なることが保証されている．

出力
q 個のクエリそれぞれについて，superpiece が元のマスから移動先のマスに到達するために必要な移動回数の最小値 m を，1 行に出力せよ．移動先のマスに到達不可能である場合は，−1 を出力せよ．

制約
1 ≤ q ≤ 1000
各クエリについて −108 ≤ a, b, c, d ≤ 108
チェス盤は全ての方向に関して無限に広い

小課題
1. (12 点) 各クエリの最初の行には，'N' がなく，'Q' がある．
2. (9 点) 各クエリの最初の行には，'Q' と 'N' の両方がある．
3. (13 点) 各クエリの最初の行には，'Q' がなく，'R' がある．
4. (8 点) 各クエリの最初の行は，常に文字列 "B" である．
5. (6 点) 各クエリの最初の行には，'Q' と 'R' がなく，'B' がある．
6. (31 点) 各クエリの最初の行は，常に文字列 "N" である．
7. (8 点) 各クエリの最初の行には，'Q'，'R'，'B' がなく，'N' がある．
8. (7 点) 各クエリの最初の行には，'Q'，'R'，'B'，'N' がなく，'K' がある．
9. (6 点) 各クエリの最初の行は，常に文字列 "P" である．
小課題は，予想される難易度の順序で並べられていないことに注意すること．

Superpiece (3 of 5)

入出力例
標準入力

標準出力

22NKP

2

3 3 5 1NKP
2 6 5 32-1

B1

2 8 3 6B
2 8 5 522

Q1

3 3 4 5QR
4 1 1 4

入出力例に関する説明
テストケース 1
最初のクエリでは， ナイト，キング，ポーンの動きを使って，(3, 3) から (5, 1) へ行くことを考える．2
回の移動でこれを行う方法は複数あり，いくつかの例を以下に示す．
ポーンとして (4, 3) へ移動した後，ナイトとして (5, 1) へ移動する．
ナイトとして (5, 2) へ移動した後，キングとして (5, 1) へ移動する．
キングとして (4, 2) へ移動した後，再びキングとして (5, 1) へ移動する．
一方，1 回の移動でこれを達成することはできない．達成するためには，ビショップまたはクイーンが必要になってしまう．
2 番目のクエリでは，(2, 6) から (5, 3) へ行くことを考える．移動回数の最小値は 2 回である．今回は，2 回ともナイトとして移動し，マス (4, 5) またはマス (3, 4) を経由しなければならない．

テストケース 2
最初のクエリでは，(2, 8) から (3, 6) へ行くことを考える．ビショップの動きだけでは，残念ながらこれを達成できない．

Superpiece (4 of 5)

2 番目のクエリでは，(2, 8) から (5, 5) へ，ビショップの動きのみを使って移動することを考える．これは 1 回の移動で達成できる．

テストケース 3
最初のクエリでは，クイーンの動きのみを使って (3, 3) から (4, 5) へ行くことを考える．たとえば (4, 4)を経由すると，2 回の移動で達成できる．
2 番目のクエリでは，クイーンとルークの動きを使って (4, 1) から (1, 4) へ行くことを考える．これは 1回の移動で達成できる．

Superpiece (5 of 5)