您正在玩一款名为 Porter Tele Porter 的角色扮演游戏。
这个游戏有两张方形陆地地图和一张海洋地图。一侧的长度就是土地图E,海图S和E<S。
当
另外,地图上的点是向东为X轴,向北为Y轴作为坐标 (X,Y)。原点是地图的最西南点。
两个地图的连接如下图所示。

该图中的海洋地图都代表相同的事物。例如图中P从该点向东走一步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)。
此时,向北、南、东、西四个方向一步的移动定义如下。 (注意: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)。
执行以下程序:
-
具有以下参数的过程 初始化(E,S):
- E -- 陆地地图大小。
- S -- 海洋地图的大小。
该过程没有返回值。 -
具有以下参数的过程 moveTo(X,Y,A,B)
在调用:
- X -- 目的地的陆地地图 x 坐标。0≤X<E 可以假设为。
- Y -- 目的地陆地地图 y 坐标。0≤Y<E。
- A、B -- 角色使用的传送(A,B)。
一次调用就是一个传送器(A,B)并多次改变方向以创建陆地地图(X,Y)。
如果可以移动,则每次调用都会返回所需的最少传送器使用次数;如果无法进行此类移动,则返回所需的最少传送器使用次数。 -1 必须作为返回值返回。
另外,无论是否可以移动。该程序返回后,该角色将显示在陆地地图上(X,Y)。
例

E=4, S=6, Q=2
考虑 的情况。
简介初始化(4,6)被调用,然后移动到 已致电是2次。
第一个电话是moveTo(2,2,3,4) 假设它是。
搬运工的位置如图所示。X(0,0)从那里开始Y(2,2)至
如果添加传送器(3,4)
使用移动。
这种情况下,如图所示,使用一次传送器即可
移动到W后,改变方向并再次使用传送器返回该位置。
到达Y。
这种移动方法最大限度地减少了传送器的使用次数,因此正确的返回值为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/(原型: 搬运工.zip)
- 参赛者实现的文件:porter.cpp
- 提交文件接口:porter.h
- 评分程序示例:grader.cpp
- 评分程序的示例输入:grader.in.1、grader.in.2、...
注意:示例评分程序按以下格式读取输入。- 1 行目: 整数 E, S, Q 用空格分隔。E是陆地地图的大小,S是海洋地图的大小,Q是移动到 已致电被调用的次数。
- 从第 2 行开始Q+1 行目:0 ≤ i < Q 对于,i+2行包含一个整数 Xi, Yi, Ai, Bi 以空格分隔。 这些整数是i+1第 在对移动到 已致电的调用中,目的地是 (Xi, Yi),并且给定的传送器是(Ai, Bi)。
- 评分器输入样本的预期输出:grader.expect.1、grader.expect.2、...
注意:示例评分程序按以下格式写入输出。
- 从第 1 行开始 对于Q行目: 0 ≤ i < Q 对于,i+1在线i+1称为 写入移动到 已致电应返回的值。