← 返回题目列表

AtCoder · ijpc_maze

B. 两只狐狸和黑暗迷宫

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

狐狸太郎和次郎正在参观狐狸游乐园。

看起来很好玩的景点有很多,但太郎似乎对迷宫景点感兴趣。二郎似乎不太热衷,但他屈服于太郎的热情,决定一起进入迷宫。

这个游乐园的迷宫有点特别。这是因为有起点和目标,并不是从起点走到终点的问题。

两只动物从迷宫的不同点开始。目的是在任何地方再次见面。

迷宫太黑了,两只动物不知道自己在哪里。当我环顾四周时,天太黑了,我什至看不到旁边有什么。 Moffle 提供了方便的 fPad 平板电脑,作为两只动物在这样的迷宫中相遇的工具。

太郎的fPad包含迷宫地图并且可以查看,但次郎的fPad不包含地图。您可以将数据从 Taro 的 fPad 发送到 Jiro 的 fPad。虽然二郎看不到地图,但他可以接收太郎的信息。

这两个 fPad 还有一项功能。使用它,您可以获得有关周围环境的一些信息。

二郎害怕黑暗的地方,所以他想尽快见到太郎。你能计算出两只动物相距多远吗?

我想尽快知道,所以最好尽可能少使用 fPad 功能。

課題

给出了有关迷宫的信息。迷宫是垂直的 由 H 横 W 矩形网格表示,每个方块要么是一面墙,要么是一条通道。迷宫的外面全是墙壁,无法穿过。

迷宫的路径为木结构,所有路径的宽度和壁厚均为1。更准确地说,本例中的迷宫是图中的任意生成树,其中顶点为一定大小的矩形中包含的网格点,两点之间有距离为1的边,将顶点和边作为路径,其他部分作为墙,然后将迷宫包围起来外墙。

図 1

図 1

图 1 显示了迷宫的示例。迷宫的大小包括周边的外墙,即在本例中 H = 7, W = 7 请注意 。

太郎和次郎在这个迷宫的某个地方,但我不知道他们在哪里。并且,保证两只动物的位置都在迷宫的通道上,并且保证两只动物所在的空间不同。

执行以下程序:

  • 具有以下参数的过程 芋头(宽、高、中):
    • W -- 迷宫的宽度。3 ≤ W ≤ 1 000 可以假设为 。
    • H -- 迷宫的高度。3 ≤ H ≤ 1 000 。W 和 在 H 都是 3 ,即可以假设至少有两个通道空间。
    • M -- 表示迷宫信息的二维整数数组。0 ≤ i < H, 0 ≤ j < W 无论 M[i][j] 从迷宫的顶部 i+1 左起第 左起第 th j+1 表示隔断是墙 1 或通道 0 。
    在此过程中 发送(b) 通过重复调用 可以向Jiro发送数据。然而 必须是 b 是 给出了 0 或 给出 1 。这个程序 二郎(W、H、S、X) 在 之前仅调用一次,并且没有返回值。
  • 具有以下参数的过程 二郎(W、H、S、X) 在:
    • W -- 迷宫的宽度。这个值是 当调用 芋头(宽、高、中) 时 匹配 W 的值。
    • H -- 迷宫的高度。这个值是 芋头(宽、高、中) 时 匹配 H 的值。
    • S -- 从 Taro 发送的数据的长度(位数)。
    • X -- S 整数的一维数组。0 ≤ i < S 无论 X[i] 是 给出了 芋头(宽、高、中) 里面 发送(b) 通过重复调用 是 时间保证在 i+1 左起第 被呼叫时 等于 b 的值。
    此程序 仅在调用 芋头(宽、高、中) 后调用一次。这个程序迷宫中太郎和次郎的最短距离 需要计算并将其作为返回值返回。然而,共享一条边的单元格之间的距离为 1。

芋头(宽、高、中) 和二郎(W、H、S、X) 在 里面 查询(dx,dy) 可以重复调用。查询(dx,dy) 是 给出了 芋头(宽、高、中) 如果在里面调用,Taro的当前位置,二郎(W、H、S、X) 在 如果在内部被调用,则从 Jiro 当前位置向右移动。 dx 下面的正方形 dy 表示移动的方块是墙。 返回 1 或通道 0 。

查询(dx,dy) 通话中 -1 000 ≤ dx, dy ≤ 1 000 必须是dx, dy 指定的方格是否在迷宫之外并不重要。如果指定迷宫的外部,则它代表一堵墙。 返回 1 。

例

W = 5, H = 7,

M = 考虑
1 1 1 1 1
1 0 1 0 1
1 0 1 0 1
1 0 0 0 1
1 1 1 0 1
1 0 0 0 1
1 1 1 1 1

的情况。太郎现在的位置是(1, 1), 二郎的当前位置是 (2, 5)。然而,从迷宫上方看 y+1 左起第 th x+1 第格(x, y)。芋头 里面 查询 调用 时的参数和返回值示例如下所示。

参数 返回值
查询(2, 0) 0
查询(-4, 3) 1
查询(3,-1) 1

另外,芋头 里面 发送 假设 被这样调用:

发送(1)
发送(0)
发送(0)
发送(1)
发送(1)

此时 二郎 通话中 S = 5 和

X =  1
0
0
1
1

变为。

在这种情况下 必须返回 二郎 是 给出了 7 。 您调用

小課題

小課題 1 (13 点)

  • 芋头(宽、高、中) 和 二郎(W、H、S、X) 在 是 给出了 查询(dx,dy) 多少次并不重要。
  • Taro 发送给 Jiro 的数据大小 (S)是 必须小于或等于 1 000 050 。 对

小課題 2 (11 点)

  • 芋头(宽、高、中) 和 二郎(W、H、S、X) 在 是 给出了 查询(dx,dy) 多少次并不重要。
  • Taro 发送给 Jiro 的数据大小 (S)是 必须小于或等于 500 000 。 对

小課題 3 (21 点)

  • 芋头(宽、高、中) 和 二郎(W、H、S、X) 在 是 时间保证在 查询(dx,dy) 的调用总数为 必须小于或等于 200 倍。
  • Taro 发送给 Jiro 的数据大小 (S)是 必须小于或等于 500 000 。 对

小課題 4 (21 点)

  • 芋头(宽、高、中) 和 二郎(W、H、S、X) 在 是 时间保证在 查询(dx,dy) 的调用总数为 必须小于或等于 120 倍。
  • Taro 发送给 Jiro 的数据大小 (S)是 必须小于或等于 500 000 。 对

子作业5(最多34分)

  • 芋头(宽、高、中) 和 二郎(W、H、S、X) 在 是 时间保证在 查询(dx,dy) 的调用总数为 必须小于或等于 120 倍。
  • Taro 发送给 Jiro 的数据大小 (S)是 必须小于或等于 500 000 。 对
  • 重要: 该子任务的得分是 由 查询(dx,dy) 被调用的总次数决定。

    此子作业的测试用例 t ,如果您提交的程序是 查询(dx,dy) 被调用的次数 Pt 。全部 Pt 的最大值 P 。您在此子任务的分数将由以下规则决定。

    • P ≤ 80 ,您将获得34分满分。
    • 80 < P < 120 那么你的分数是 ((120-P) / 40) 这是2 * 33 +1 的值四舍五入到小数点。
    • P≥120 如果 甚至其中一项输出不正确,您的得分为 0 分。

实施细节

制限

  • CPU时间限制:1秒
  • 内存限制:256 MB
    注意: 堆栈的大小没有固定限制。作为堆栈使用的内存包含在总内存使用量中。

接口 (API)

  • 实现文件夹:maze/(原型: maze.zip)
  • 参赛者实现的文件:maze.cpp
  • 提交文件接口:maze.h
  • 评分程序接口:grader.h
  • 评分程序示例:grader.cpp
  • 评分程序的示例输入:grader.in.1、grader.in.2、...
    注意:示例评分程序按以下格式读取输入。
    • 1 行目: 整数 W, H, tY, tX, jY, jX 用空格分隔。tY, tX 是Taro初始位置的坐标,jY, jX 表示Jiro初始位置的坐标。
    • 从第 2 行开始 H+1 行目: 0 ≤ i < H , 它被定义为连接i+2 在线 W 字符串 M[i] 用空格分隔。0 ≤ j < W , 它被定义为连接M[i][j] 从迷宫上方 左起第 i+1 左起第 左起第 th j+1 表示第一个方块是墙。'#'或段落'.'。
  • 评分器输入样本的预期输出:grader.expect.1、grader.expect.2、...
    注意:示例评分程序按以下格式写入输出。
    • 第 1 行:过程 写入 二郎 应返回的值。
  • 示例评分程序按以下格式将信息写入标准错误输出。
    • 1 行目: "S = 输出 S"。但是, S 在本次运行中 调用 发送 假设 的次数。
    • 2 行目: "#查询= P"。但是, P 在本次运行中 调用 查询 调用 的次数。