#559. 「LibreOJ Round #9」ZQC 的迷宫

内存限制:512 MiB 时间限制:5000 ms 题目类型:交互
上传者: Snakes

题目描述

请注意最下方添加内容。

本题是一道交互题。

位于 n×mn\times m 个方格组成的黑暗迷宫的你,需要走到这个迷宫的终点,以完成迷宫挑战。

最开始,你位于迷宫的起点即 (1,1)(1,1) 处,且面向右侧,终点位于 (n,m)(n,m) 处。迷宫中任意两个方格之间均联通,且仅有唯一的一条路径,两个相邻(即上、下、左、右四联通)方格间长度为一个单位长度。两个相邻方格之间可能会有墙壁,墙壁厚度相对于方格而言非常小,粗略不计。迷宫的边界均有墙壁,且每一堵墙壁均与边界联通。迷宫是完全黑暗的,这意味着,你无法得到除 n,mn,m 以外的任何信息。

为了在黑暗条件下尽量不迷路,每次前进时你只能从当前格子出发,沿着左侧或右侧墙壁,左手或右手扶着墙壁前进,并且使扶着墙壁的手移动距离恰好为一个单位长度。需要注意的是,若左侧或右侧墙壁不存在,则沿该侧方向无法前进。

在黑暗中过久的你会感到恐惧,因此你需要在你尽早走出迷宫。如果你没有在限定步数内走出迷宫,挑战将会失败。

下图表示一个迷宫的例子,以及一个可行的前进方法:

Explanation_LR9A.png

交互方式

可供调用的操作有:

  1. move_left 表示沿左侧前进一个单位长度。返回值为 0 表示操作不合法,为 1 表示操作合法。
  2. move_right 表示沿右侧前进一个单位长度。返回值为 0 表示操作不合法,为 1 表示操作合法。
  3. reverse 表示向后转,即面向方向旋转 180180^\circ,位置不变。无返回值。
  4. reach_dest 表示询问是否到达终点。返回值为 0 表示未到达终点,为 1 表示到达终点且交互器会自动退出。
  5. dist 表示询问当前位置与终点的最短距离。返回值即为最短距离。

当你想要进行某个操作时,请向标准输出流 stdout 中写入如下格式的字符串:

<操作名称>

必须在请求后追加换行符;多余的空白字符将被自动忽略。

在收到用户程序发送的请求后,交互器会向用户程序的标准输入流 stdin 中发送返回值。你只需在你的程序中使用通常的办法读入这个值,就好像是从控制台或文件中读取内容一样。交互器将在发送返回值后再附加一个换行符 \n,以便于用户程序读入。本题目的操作返回值都是数字,因此直接读入数字即可。

请注意,很多语言的输入与输出库都会带有缓存,请在写入操作请求后手动刷新缓存,以确保请求顺利递送。

C++ 语言可以这样刷新缓存(std::endl 会自动刷新缓存):

std::cout << value << std::endl << std::flush;
// or std::cout << value << std::endl;

C 语言可以这样刷新缓存:

printf("%d\n",value);
fflush(stdout);

Pascal 语言可以这样刷新缓存:

writeln(value);
flush(output);

其它语言的刷新缓存方法请自行查阅资料。

确定抵达终点后,调用 reach_dest 操作后即可结束程序。交互器退出时,如果用户程序还在运行,就会被立即终止,但不会引发超时错误。

由于交互请求发送与返回值接收过程受到缓存区影响,请务必接收返回值以避免非预期情况发生。保证交互库在 1s1\text{s} 内至少可完成 1.8×1051.8 \times 10^5 次交互操作,也即对于限制操作次数最小值 600002600002,调用交互操作 600002600002 次并接收返回值所耗时间至多不超过 3.5s3.5\text{s},这意味着选手至少有 1.5s1.5\text{s} 的运行时间。

若评测结果返回 Time Limit Exceeded 且非时间复杂度方面原因,请注意程序是否已经在写入操作请求后刷新缓存,或是程序是否一直尝试进行不合法的前进操作。返回 Invalid Interaction 请注意程序是否尝试调用不存在的操作。

任务

你需要提交一个程序,使用上述操作完成迷宫挑战。

在初始时,交互器会向用户程序的标准输入流 stdin 中发送一行四个整数 n,m,l,dn, m, l, d。其中,参数 nn 表示迷宫长度,mm 表示迷宫宽度,ll 表示可供调用的前进操作次数,dd 表示可供调用的询问距离操作次数。需要注意的是,前进操作包括 move_leftmove_right,也即调用二者之一均会减少可供调用的前进操作次数,不合法操作不被计入函数调用次数统计。询问距离操作即 dist 操作。

在操作次数用尽后,该操作将不会执行并返回预期结果,而会返回 0。若前进操作调用次数用尽且未抵达终点,交互器将会终止用户程序运行。

评分方式

对于每个测试点,令 pp 表示起点与终点的距离,qq 表示无可用前进操作次数时或抵达终点调用 reach_dest 操作后,你所在位置与终点的距离,该测试点得分百分比为 max(pqp,0)\max({p-q \over p},0)

对于每个子任务,其得分为该子任务分值与每个测试点得分百分比的乘积。

若对交互器作出攻击,得分将作无效处理。

如何在本地测试你的程序

由于评测机压力过大,现在下发本题交互器与相同规模测试数据。对选手造成的不便深表歉意。请确保您能拿到尽量高的分数后在接近比赛结束时提交。

文件解压后有如下文件:

interactor.exe
interactor.cpp
interactor
input1
input2
input3
input4
input5

其中 input* 对应该子任务范围的数据,测试前,你需要将其重命名为 input

Windows 系统

对于使用 Windows 系统的选手,你需要在与 interactor.exe 同一目录下放置 input 文件,用于输入交互器数据,若选手程序为 user.exe,请运行以下指令:

user.exe <&1 | interactor.exe >&0

该指令将输出评测结果 Mission Completed.Mission Failed.,同时将在同一目录下生成 score.txt,表示该测试点得分百分比。若为 -1,则表示不合法交互操作。

Linux 发行版系统

对于使用 Linux 发行版的选手,你需要在与 interactor 同一目录下放置 input 文件,用于输入交互器数据,若选手程序为 user,请运行以下指令:

{ ./interactor < /dev/fd/3 | ./user 3>&-; } 3>&1 | :

该指令将输出评测结果 Mission Completed.Mission Failed.,同时将在同一目录下生成 score.txt,表示该测试点得分百分比。若为 -1,则表示不合法交互操作。

其他系统

对于使用 MacOS 等系统的选手,请自行编译 interactor.cpp,并参照上述方法测试你的程序。

数据范围与提示

对于所有数据,保证 1n,m5001\leq n,m\leq 500l,dl,d 限制见下表。

子任务编号分值n,mn,m\leqll\geqdd\geq
1101010102333233323332333
215155050666666666666666666
319191001002500022500021000010000
424242002005000025000022000020000
53232500500500002500002100000100000