12451번 - 無限庭園 (Small) 다국어

パスカル王国の王様は迷路が大好きである。あるとき王様は家臣に、お城の広大な庭を覆うような迷路を作れと命じた。 これは大変な指示だった。なぜなら、お城の庭は無限に広いからである。 原点をお城の位置に置き、X 軸方向を東に、Y 軸方向を北にとると、庭は X≥0, Y≥0 となる領域全体に広がっている。

ここで、素晴らしいロボット工学専門家であるあなたは、庭仕事ロボットを改良して、庭に迷路を描くロボットを作ってしまった。 このロボットは A, B 2 つのモードと、 "L,X,R" の文字が続けて書かれたテープ、そしてテープの一箇所を指す読取ヘッダからなる。ロボットはテープの読取ヘッダが指す文字を読み、それに従って動きを変えることができる。読取ヘッダは前から後ろに、一方向に読むことしかできないが、ロボットは今まで読んだテープを含むテープ全体をコピーしてテープの末端に貼り付けることで、テープをさらに読み進めることができる。また、ロボットはテープの任意の箇所を書き換えることができる。

ロボットは以下の処理を順に行う。

• 読取ヘッダがテープの最後の文字を指している場合、モードに応じて以下のどちらかの処理を行う。
  • ロボットが A モードの場合、テープの最初の文字を "X" であれば "L" に、 "L" であれば "X" に書き換える。その後テープ全体をコピーし、コピーしたテープ中の "L" を "R" に、 "R" を "L" に書き換えた上でテープの最後に追加する。その後、モードを B モードとする。
  • ロボットが B モードの場合、テープ全体をコピーし、その前後をひっくり返した上でテープの最後に追加する。その後、モードを A モードとする。
• 前方に距離 2 だけ進み、読取ヘッダをひとつ進ませる。
• 読取ヘッダに書いてある文字を読む。文字が "L" なら左に 90 度回転、 "R" なら右に 90 度回転する。 "X" の場合は何もしない。
• ここまでの処理を繰り返す。

このロボットを座標 (1,1) に置き、Y 軸方向正の向きを向かせ、 "X" 一文字だけ書かれたテープを読ませる。ロボットの初期状態は A モードで、読取ヘッダは文字 "X" を指している。ここでロボットを起動すると、ロボットは庭を無限に走り続ける。このロボットの軌跡を迷路の壁とすると、複雑な迷路ができることがわかった。王様はあなたのこの業績を褒めた。

図は、ロボットがはじめにどのように振る舞うかを表している。座標 (1, 1) からスタートしたロボットは、直後にテープを追加して北に長さ 2 だけ直進し、東へ方向転換する。その後、図のように進んでゆく。

さて、この迷路が複雑すぎて中から出て来られなくなるとそれはそれで問題である。王様はあなたに、このロボットが描いた迷路を検証するよう命じた。検証のために、あなたは迷路内の指定された 2 点間の最短距離を求めるプログラムを作ることにした。

プログラムは、2 点 P, Q の座標が与えられ、これらの迷路内での最短距離を出力する。簡単のために、距離を測るための道のりは X 軸に垂直あるいは平行な線分のみで構成されるとする。また、壁は通り抜けることはできないものの、壁自体は限りなく薄く、壁のある線にはいくらでも近づけるとする。

最初の行はテストケースの個数 T を表す正の整数である。それ以降の行に、T 個のケースを表すデータが続く。

それぞれのテストケースは、スペースで区切られた 4 つの偶数からなる 1 行の文字列で表現される。これらの偶数は、順番に Px, Py, Qx, Qy を表す。

点 (Px, Py), (Qx, Qy) はともに、迷路の壁のない点を指している。これは、迷路の壁の座標が必ず奇数を含むことから明らかである。

制限

• 0 ≤ Px, Py, Qx, Qy.
• 1 ≤ T ≤ 100.
• 0 ≤ Px, Py, Qx, Qy ≤ 32.

それぞれのテストケースについて、

Case #X: L

という 1 行の文字列を出力せよ。ここで、X は 1 から始まるテストケースの番号であり、L は点 P から点 Q までの、本文中で定義された道のりを通った場合の最短距離である。