Time Limit: 0 msec / Memory Limit: 256 MB
あなたはポーター・テレ・ポーターというロールプレイングゲームをプレイしている。
このゲームには、二つの正方形の陸マップと海マップがある。一辺の長さは陸マップがE、海マップがSであり、E<Sである。
また、マップ上の地点は東向きをX軸、北向きをY軸として座標(X,Y)で表される。原点はマップの最も南西にある地点である.
2つのマップは下の図のように繋がっている。
この図での海マップは全て同じものを表している。例えば、図中のP点から東に1歩進むとQ点に到達する。
このゲームではあなたはポーター(荷物運搬人)というキャラクターとして行動する。
ポーターはマップ上で東西南北のいずれかの向きを向いていて,陸と海のどちらもマップ上も移動できる。
ゲームが始まった時、ポーターは陸マップの(0,0)にいて、ポーターには荷物を運ぶ目的地を表す陸マップの座標(X,Y)と、テレポーター(A,B)という装置が与えられる。
テレポーター(A,B)のスイッチを押すと、今いる位置からA歩前進し左に曲がってB歩前進したときの位置に一瞬で移動することができる。
ポーターは疲れたくないので、与えられたテレポーター(A,B)と方向転換だけを使って目的地(X,Y)へ移動したいと考えている。
テレポーターと方向転換だけで移動することが不可能な場合、ポーターは徒歩または泳ぎで目的地(X,Y)に移動する。
何らかの方法でポーターが目的地(X,Y)に到達すると、そこで新たな目的地の座標とテレポーターが与えられ、ゲームは続行する。
新たな目的地への移動では新たに与えられたテレポーターを使い、もともと持っていたテレポーターは使うことができない。
あなたは、目的地のそれぞれに行く過程において、ポーターがテレポーターと方向転換だけで目的地にたどり着けるか、またそのとき何回テレポーターを使えば良いかを知りたくなった。
課題
一辺の長さEの正方形の陸のマップと、一辺の長さSの正方形の海のマップがある。 二つのマップ上の点は座標で表され、海のマップでは (Sx,Sy)(Sx,Syは整数、0≦Sx<S,0≦Sy<S)、陸のマップでは(Ex,Ey)(Ex,Eyは整数、0≦Ex<E,0≦Ey<E)である。
この時、東西南北4方向への一歩の移動を次のように定義する。(注意:x軸は東向き、y軸は北向きである。)
- 陸の東端(E-1,y)から東に進むと海の西端(0,y)に出て、海の西端(0,y)から西に進むと陸の東端(E-1,y)に出る。(0≦y<E)
- 陸の南端(x,0)から南に進むと海の北端(x,S-1)に出て、海の北端(x,S-1)から北に進むと陸の南端(x,0)に出る。(0≦x<E)
- 陸の西端(0,y)から西に進むと海の東端(S-1,S-E+y)に出て、海の東端(S-1,S-E+y)から東に進むと陸の西端(0,y)に出る。(0≦y<E)
- 陸の北端(x,E-1)から北に進むと海の南端(S-E+x,0)に出て、海の南端(S-E+x,0)から南に進むと陸の北端(x,E-1)に出る。(0≦x<E)
- 海の西端(0,E+y)から西に進むと海の東端(S-1,y)に出て、海の東端(S-1,y)から東に進むと海の西端(0,E+y)に出る。(0≦y<S-E)
- 海の北端(E+x,S-1)から北に進むと海の南端(x,0)に出て、海の南端(x,0)から南に進むと海の北端(E+x,S-1)に出る。(0≦x<S-E)
- 上のいずれの場合にも当てはまらないとき、
- 陸の(x,y)から、東に進むと陸の(x+1,y)、南に進むと陸の(x,y-1)、西に進むと陸の(x-1,y)、北に進むと陸の(x,y+1)に出る。(0≦x<E、0≦y<E)
- 海の(x,y)から、東に進むと海の(x+1,y)、南に進むと海の(x,y-1)、西に進むと海の(x-1,y)、北に進むと海の(x,y+1)に出る。(0≦x<S、0≦y<S)
また、キャラクターがいる位置と向きからA歩前に進み、左に曲がってB歩前に進むことを、合わせてテレポーター(A,B)を使うと定義する。
次のプロシージャを実装せよ:
-
次のパラメータを持つプロシージャ init(E,S):
- E -- 陸のマップの大きさ。
- S -- 海のマップの大きさ。
このプロシージャは戻り値を持たない。 -
次のパラメータを持つプロシージャ moveTo(X,Y,A,B):
- X -- 行き先の陸のマップのx座標。0≦X<Eを仮定して良い。
- Y -- 行き先の陸のマップのy座標。0≦Y<Eを仮定して良い。
- A,B -- キャラクターが使うテレポート(A,B)を表す。
1回の呼び出しはキャラクターが今いる位置からテレポーター(A,B)と方向転換を複数回使って陸のマップの(X,Y)へ移動することに対応している。
それぞれの呼び出しは、移動が可能な場合は必要なテレポーターの使用回数の最小値を、そのような移動が不可能な場合は -1 を戻り値として返す必要がある。
また、移動が可能か不可能かに関わらず、このプロシージャが戻り値を返した後にはキャラクターは陸のマップの(X,Y)にいなければならない。
例
E=4, S=6, Q=2 の場合を考える.
はじめにinit(4,6)が呼ばれ,その後moveToが2回呼ばれる.
1回目の呼び出しがmoveTo(2,2,3,4)だったとする.
ポーターが居る位置は図の地点X(0,0)であり,そこから地点Y(2,2)にテレポーター(3,4)を使って移動する.
この場合,図のように,テレポーターを1回使って地点Wに移動した後,方向転換してもう一度テレポーターを使うと地点Yに到達する.
この移動方法はテレポーターの使用回数が2回で最小となるので,正しい戻り値は2である.
その後の2回目の呼び出しがmoveTo(1,3,2,2)だったとする.
ポーターの居る位置は地点Y(2,2)であり,目的地は地点Z(1,3)である.
しかし,地点Yからテレポーター(2,2)と方向転換だけを使って地点Zに行くことはできないので.正しい戻り値は-1である.
この呼び出しのあと,ポーターは地点Zに移動する.
小課題
小課題 1 (21 点)
- 1 ≦ E < S ≦ 1 000
- 0 ≦ A ≦ 20
- 0 ≦ B ≦ 20
- Q = 1
小課題 2 (27 点)
- 1 ≦ E < S ≦ 1 000
- 0 ≦ A ≦ 1 000 000 000
- 0 ≦ B ≦ 1 000 000 000
- 1 ≦ Q ≦ 10
小課題 3 (52 点)
- 1 ≦ E < S ≦ 100 000
- 0 ≦ A ≦ 1 000 000 000
- 0 ≦ B ≦ 1 000 000 000
- 1 ≦ Q ≦ 100 000
実装の詳細
制限
- CPU 時間制限: 2秒
- メモリ制限: 256 MB
注意: スタックのサイズには決められた制限はない。スタックとして使用されたメモリは、メモリ総使用量に含まれる。
インターフェース (API)
- 実装フォルダ: porter/ (プロトタイプ: porter.zip)
- 競技者が実装するファイル: porter.cpp
- 提出ファイルのインターフェース: porter.h
- 採点プログラムのサンプル: grader.cpp
- 採点プログラムの入力のサンプル: grader.in.1, grader.in.2, ...
注意:採点プログラムのサンプルは次の書式の入力を読み込む。- 1 行目: 整数 E, S, Q が空白区切りで書かれている.Eは陸のマップの大きさ,Sは海のマップの大きさ,QはmoveToが呼ばれる回数を表す.
- 2 行目からQ+1 行目:0 ≦ i < Qに対し,i+2行には,整数 Xi, Yi, Ai, Bi が空白区切りで書かれている. これらの整数は,i+1回目のmoveToの呼び出しにおいて,目的地が(Xi, Yi)で,与えられたテレポーターが(Ai, Bi)であることを表す.
- 採点プログラムの入力のサンプルに対して期待される出力: grader.expect.1, grader.expect.2, ...
注意:採点プログラムのサンプルは次の書式の出力を書き出す。
- 1行目からQ行目: 0 ≦ i < Qに対して,i+1行目にはi+1回目に呼び出されたmoveToが返すべき値が書かれている.