QOJ.ac

QOJ

Time Limit: 10 s Memory Limit: 512 MB Total points: 100 Interactive

# 8361. maze

Statistics

题目背景:出题人已经不会写背景了。

这是一道交互题

Z 找到了一个年代非常久远的游戏机,这个游戏机上有一个非常简单的游戏:

有一个迷宫,它可以看成由 $n$ 行 $m$ 列的方格组成。一些相邻的格子间可以双向通行,但还有一些相邻的格子间被墙阻隔。

为了增加一点游戏的趣味性,这个迷宫满足任意两个方格之间,正好有一条简单路径(不经过重复方格)。为了保证游戏的多样性,所有的迷宫都使用随机方式生成。具体的生成方式为,将所有可能的墙排成一列,然后随机打乱,接下来按顺序考虑所有墙,如果加入这堵墙后迷宫仍然连通就加入这堵墙。可以发现这样一定能生成一个合法的迷宫。

Z 需要操控一个人物从 $(1,1)$ 走到 $(n,m)$,游戏机有四个方向按键,对应上下左右。小 Z 按下一个方向键时,人物会向对应方向走一个格子。如果这个方向上是墙,则这次移动失败,否则这次移动成功。

游戏中一关的过程为,初始人物在 $(1,1)$,小 Z 可以任意按方向键,人物到达 $(n,m)$ 时就通过了这一关。

Z 想要通关这个游戏,但很不幸的是,游戏机的屏幕坏了,因此小 Z 看不到迷宫中的状态(墙的位置以及当前人物的位置),小 Z 只能通过屏幕边界判断迷宫的大小。

幸运的是,这个游戏中,每次按下方向键后游戏机会根据这次移动是否成功发出不同的震动,因此小 Z 希望用这个信息来通过游戏。但因为年久游戏机失修,这个震动存在延迟。具体来说,存在一个非负整数 $d$,第 $i$ 次操作的结果会在第 $i+d$ 次操作后反馈(即在第 $i+d+1$ 次操作之前,你可以知道第 $i$ 次操作对应的移动是否成功)。通过一些尝试,小 Z 已经知道了 $d$ 的值。

Z 还是想要通过这个游戏,但他还要去写题面,因此他只能在每一关中进行不超过 $t$ 次操作。因此你需要写一个程序,模拟小 Z 的操作过程,并帮助小 Z 在ddl之前通关。

游戏可能存在多个关卡,因此你可能需要解决多次问题。

交互方式

你需要包含头文件 maze.h

你需要实现如下两个函数:

void init(int n,int m,int d,int t);

这个函数用来进行每组数据前的初始化操作。调用这个函数也表示上一组数据的交互过程已经结束。

int move(int is);

这个函数用来进行移动的过程,传入变量为上次反馈的结果,你需要返回这次操作移动的方向。

具体来说,设这是第 $x$ 次调用 move,如果 $x\leq d+1$,则不存在反馈,传入的 $is=-1$。否则,如果第 $x-d-1$ 次移动操作是成功的,则传入的 $is=1$,如果移动不成功则传入的 $is=0$。

你需要返回一个 $[0,3]$ 间的整数,表示移动的方向。$0,1,2,3$ 分别表示向上,向下,向左,向右。即从当前位置 $(x,y)$ 分别移动到 $(x-1,y),(x+1,y),(x,y-1),(x,y+1)$。

交互过程为:

对于每组数据,首先调用一次 init,接下来多次调用 move,交互库按照 move 的返回值进行移动,重复这一过程直到到达终点或者出现不合法的操作(次数超过限制或者返回值不合法)后结束这组数据的交互过程,随后开始下一组数据的交互。

你可以参考下发文件中的 grader.cppmaze_sample.cpp 以及样例输入文件以更好地理解交互过程。如果还有疑问可以提问出题人

你可以使用如下方式编译下发交互库:

g++ -o grader grader.cpp maze.cpp -O2 -std=c++11

其中 maze.cpp 是你的程序。

样例交互库使用如下方式读入:

首先输入一个非负整数 $T$,表示数据组数。接下来依次输入每一组数据:

首先输入一行四个正整数 $n,m,d,t$,含义见题面。

接下来输入 $2n+1$ 行,每行一个长度为 $2m+1$,包含 o-| 以及空格的字符串,表示迷宫的状态。具体输入格式可以参考下发文件,以下是一个简单的输入文件例子:

1
2 4 6 10000
o-o-o-o-o
| |     |
o o o-o o
|   |   |
o-o-o-o-o

在每组数据的交互过程结束后,样例交互库会输出这组数据使用的操作次数。如果出现不合法操作,交互库会输出对应错误信息并停止。

如果成功地完成了每一组数据的交互,则最后交互库会输出所有数据中使用的操作次数之和。

下发文件中的 maze_sample.cpp 是一个提交程序的示例,它可以通过第一组下发数据。

数据范围与限制

设 $T$ 为数据组数,即调用 init 的次数。

对于所有数据,保证 $1\leq n,m\leq 20,0\leq d\leq 100$,保证迷宫按照题目描述中给出的方式生成,且迷宫在交互开始前已经确定。

子任务编号 子任务分值 特殊限制
$1$ $15$ $d=0,t=2\times 10^4,T=5$
$2$ $15$ $n,m\leq 10,t=2.5\times10^4,T=5$
$3$ $20$ $t=2\times 10^4,T=5$
$4$ $15$ $t=10^4,T=5$
$5$ $35$(特殊计分方式) $t=3\times 10^4,T=10$

前四个子任务中,每个子任务包含不超过 $4/3/6/6$ 个测试点。如果你通过了一个测试点内的所有数据则获得满分,否则不得分。

最后一个子任务包含不超过 $10$ 个测试点,计分方式如下:

如果存在不合法的操作或者出现 TLERE 等状态,则分数为 $0$ 分。否则按照如下方式计算分数:

对于一组数据,记你使用的操作次数为 $t_i$。则你最后的得分为:$35*\min(1,\frac{\max(10^5-(\sum t_i),0)}{7\times 10^4})$

子任务得分取每个测试点得分的最小值。