这是一个交互问题。
在坐标平面的 $$$(1, 1)$$$ 到 $$$(n, n)$$$ 位置上有一个由 $$$n$$$ 组成的传送带网格。平面上的所有其他方格都是空的。每条传送带均可配置为向上 ('^')、向下 ('v')、向左 ('<') 或向右 ('>') 移动箱子。如果一个盒子移动到一个空的方块上,它就会停止移动。
然而,$$$n^2$$$ 皮带之一被卡住,并且无论如何配置,它总是会朝同一方向移动箱子。您的目标是执行一系列测试,以确定哪条传送带被卡住,以及它发送物品的方向。
为此,您最多可以执行 $$$25$$$ 测试。在每次测试中,您为所有 $$$n^2$$$ 传送带指定一个方向,在其中一个传送带顶部放置一个盒子,然后打开所有传送带。
$$$n=4$$$ 查询的一种可能结果。在本例中,该框从 $$$(2, 2)$$$ 开始。如果没有卡住的传送带,它最终会到达 $$$(5, 4)$$$,但由于“>”传送带卡在 $$$(3, 3)$$$,它会进入无限循环。
传送带移动箱子的速度太快,您无法看到,因此您从测试中收到的唯一信息是箱子是否最终停止移动,如果是,则其最终位置的坐标。
互动
您可以通过读取单个整数 $$$n$$$ ($$$2 \le n\le 100$$$) 开始交互 - 网格中的行数和列数。
然后,您最多可以进行 $$$25$$$ 查询。
每个查询应以 ? 形式的行开头r c,其中 r 和 c 分别是框的初始行和列。
查询的接下来的 $$$n$$$ 行每行应包含 $$$n$$$ 个字符。第 $$$i$$$ 行的第 $$$j$$$ 个字符应为 '^'、'v'、'<' 或 '>' 之一,指示此查询的传送带 $$$(i, j)$$$ 的方向。
每次查询后,您将收到两个整数 $$$x$$$ 和 $$$y$$$。如果$$$x = y = -1$$$,则盒子进入无限循环。否则,它的最终位置是$$$(x, y)$$$。
如果您查询过多或查询无效,您将收到错误答案判决。
找到卡住的传送带及其方向后,打印一行! r c dir,其中r和c分别是卡住输送机的行和列,dir是'^'、'v'、'<'或'>'之一,指示卡住输送机的方向。请注意,打印此答案不会计入您的 $$$25$$$ 查询总数。打印此行后,您的程序应该终止。
交互器是非自适应的。这意味着卡住的皮带的位置和方向在交互开始时是固定的,并且在查询后不会改变。
打印查询后,不要忘记输出行尾并刷新输出。否则,您将超出空闲限制。为此,请使用:
- C++ 中的 fflush(stdout) 或 cout.flush();
- Java 中的 System.out.flush();
- 帕斯卡刷新(输出);
- Python 中的 stdout.flush() ;
- 请参阅其他语言的文档。
黑客
要进行破解,请使用以下格式。
第一行应包含一个整数 $$$n$$$ ($$$1 \le n \le 100$$$) — 网格中的行数和列数。
下一行应包含两个整数 $$$r$$$ 和 $$$c$$$ ($$$1 \le r, c \le n$$$),以及一个字符 $$$\mathrm{dir}$$$ ($$$\mathrm{dir}$$$ 是 '^', 'v', '<', '>' 之一) — 卡住的传送带及其位置固定方向。这些值应该用空格分隔。
示例
输入 #1
3 -1 -1 0 2
输出 #1
? 2 2 >>< >>v ^<< ? 1 1 >>< >>v ^<< ! 1 2 ^
输入 #2
4 -1 -1
输出 #2
? 2 2 v>v< ^v<v v>v^ >v>v ! 3 3 >
注意
对于第一个示例输入的第一个查询,框从 $$$(2, 2)$$$ 开始,并进入包含行 $$$2$$$ 和 $$$3$$$ 的无限循环。由于卡住的传送带位于 $$$1$$$ 行,因此它不会影响查询的结果。
对于第一个示例输入的第二个查询,传送带以相同的方式配置,但框从 $$$(1, 1)$$$ 开始。如果没有卡住的传送带,它将进入 $$$(1, 2)$$$ 和 $$$(1, 3)$$$ 之间的无限循环。然而,卡住的传送带将其重定向到 $$$(0, 2)$$$。
在这两个查询之后,程序能够确定卡住的传送带位于 $$$(1, 2)$$$ 并将物品向上引导。
第二个示例输入的查询对应于上图。询问后,传送带卡住的可能性有很多,但程序正确地猜测它位于 $$$(3, 3)$$$ 并将物品引导到右侧。