狐狸太郎和次郎正在参观狐狸游乐园。
看起来很好玩的景点有很多,但太郎似乎对迷宫景点感兴趣。二郎似乎不太热衷,但他屈服于太郎的热情,决定一起进入迷宫。
这个游乐园的迷宫有点特别。这是因为有起点和目标,并不是从起点走到终点的问题。
两只动物从迷宫的不同点开始。目的是在任何地方再次见面。
迷宫太黑了,两只动物不知道自己在哪里。当我环顾四周时,天太黑了,我什至看不到旁边有什么。 Moffle 提供了方便的 fPad 平板电脑,作为两只动物在这样的迷宫中相遇的工具。
太郎的fPad包含迷宫地图并且可以查看,但次郎的fPad不包含地图。您可以将数据从 Taro 的 fPad 发送到 Jiro 的 fPad。虽然二郎看不到地图,但他可以接收太郎的信息。
这两个 fPad 还有一项功能。使用它,您可以获得有关周围环境的一些信息。
二郎害怕黑暗的地方,所以他想尽快见到太郎。你能计算出两只动物相距多远吗?
我想尽快知道,所以最好尽可能少使用 fPad 功能。
課題
给出了有关迷宫的信息。迷宫是垂直的 由 H 横 W 矩形网格表示,每个方块要么是一面墙,要么是一条通道。迷宫的外面全是墙壁,无法穿过。
迷宫的路径为木结构,所有路径的宽度和壁厚均为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 。
- 具有以下参数的过程 二郎(W、H、S、X)
在:
- W -- 迷宫的宽度。这个值是 当调用 芋头(宽、高、中) 时 匹配 W 的值。
- H -- 迷宫的高度。这个值是 芋头(宽、高、中) 时 匹配 H 的值。
- S -- 从 Taro 发送的数据的长度(位数)。
- X -- S 整数的一维数组。0 ≤ i < S 无论 X[i] 是 给出了 芋头(宽、高、中) 里面 发送(b) 通过重复调用 是 时间保证在 i+1 左起第 被呼叫时 等于 b 的值。
芋头(宽、高、中) 和二郎(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), 二郎的当前位置是 (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 在本次运行中 调用 查询 调用 的次数。