← 返回题目列表

AtCoder · ijpc_porter

C. 波特-远程波特

中文机器翻译题面 查看原题

您正在玩一款名为 Porter Tele Porter 的角色扮演游戏。

这个游戏有两张方形陆地地图和一张海洋地图。一侧的长度就是土地图E,海图S和E<S。 当
另外,地图上的点是向东为X轴,向北为Y轴作为坐标 (X,Y)。原点是地图的最西南点。

两个地图的连接如下图所示。
porter-fig1.png
该图中的海洋地图都代表相同的事物。例如图中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) 在调用之前仅调用一次。
    该过程没有返回值。
  • 具有以下参数的过程 moveTo(X,Y,A,B) 在调用:
    • X -- 目的地的陆地地图 x 坐标。0≤X<E 可以假设为。
    • Y -- 目的地陆地地图 y 坐标。0≤Y<E。
    • A、B -- 角色使用的传送(A,B)。
    此程序 已致电Q次。
    一次调用就是一个传送器(A,B)并多次改变方向以创建陆地地图(X,Y)。
    如果可以移动,则每次调用都会返回所需的最少传送器使用次数;如果无法进行此类移动,则返回所需的最少传送器使用次数。 -1 必须作为返回值返回。
    另外,无论是否可以移动。该程序返回后,该角色将显示在陆地地图上(X,Y)。

例

porter-fig2.png
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称为 写入移动到 已致电应返回的值。