← 返回题目列表

Codeforces · 1205/C

C. 回文路径

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

这是一个交互问题

给你一个网格 $$$n\times n$$$,其中 $$$n$$$ 是奇数。行从上到下从 $$$1$$$ 到 $$$n$$$ 列举,列从左到右从 $$$1$$$ 到 $$$n$$$ 列举。单元格位于行 $$$x$$$ 和列 $$$y$$$ 的交叉点上,用 $$$(x, y)$$$ 表示。

每个单元格包含 $$$0$$$ 或 $$$1$$$。已知左上角单元格包含$$$1$$$,右下角单元格包含$$$0$$$。

我们想知道网格中所有单元格中的数字。为此,我们可以提出以下问题:

"$$$?$$$ $$$x_1$$$ $$$y_1$$$ $$$x_2$$$ $$$y_2$$$",其中 $$$1 \le x_1 \le x_2 \le n$$$、$$$1 \le y_1 \le y_2 \le n$$$ 和 $$$x_1 + y_1 + 2 \le x_2 + y_2$$$。换句话说,我们输出网格的两个不同的单元格$$$(x_1, y_1)$$$, $$$(x_2, y_2)$$$,这样我们可以通过仅向右和向下移动从第一个单元格到第二个单元格,并且它们不相邻。

作为对此类问题的回答,您将被告知 $$$(x_1, y_1)$$$ 和 $$$(x_2, y_2)$$$ 之间是否存在路径,仅向右或向下,其中单元格中的数字形成回文。

例如,以绿色显示的路径是回文路径,因此回答“$$$?$$$ $$$1$$$ $$$1$$$ $$$2$$$ $$$3$$$" 和 "$$$?$$$ $$$1$$$ $$$2$$$ $$$3$$$ $$$3$$$" 就表示存在这样的路径。但是,$$$(1, 1)$$$ 和 $$$(3, 1)$$$ 之间不存在回文路径。

通过询问不超过 $$$n^2$$$ 问题来确定网格的所有单元格。可以证明答案总是存在的。

输入

第一行包含奇数整数 ($$$3 \le n < 50$$$) — 网格的边。

互动

您通过阅读 $$$n$$$ 开始交互。

要询问有关单元格 $$$(x_1, y_1), (x_2, y_2)$$$ 的问题,请在单独的行中输出“$$$?$$$ $$$x_1$$$ $$$y_1$$$ $$$x_2$$$ $$$y_2$$$"。

查询中的数字必须满足 $$$1 \le x_1 \le x_2 \le n$$$、$$$1 \le y_1 \le y_2 \le n$$$ 和 $$$x_1 + y_1 + 2 \le x_2 + y_2$$$。不要忘记“冲洗”以获得答案。

作为响应,如果存在从 $$$(x_1, y_1)$$$ 到 $$$(x_2, y_2)$$$ 的路径(仅向右或向下),您将收到 $$$1$$$,其中单元格中的数字形成回文,否则为 $$$0$$$。

如果您的查询无效或您提出的查询超过 $$$n^2$$$ 查询,程序将打印 $$$-1$$$ 并完成交互。您将收到错误答案判决。确保立即退出,以避免得到其他判决。

当确定所有单元格中的数字时,输出“!”。

然后输出$$$n$$$行,其中第$$$i$$$是长度为$$$n$$$的字符串,对应网格第$$$i$$$行中的数字。

打印查询后,不要忘记输出行尾并刷新输出。否则,您将超出空闲限制。为此,请使用:

- C++ 中的 fflush(stdout) 或 cout.flush();
- Java 中的 System.out.flush();
- 帕斯卡刷新(输出);
- Python 中的 stdout.flush() ;
- 请参阅其他语言的文档。

黑客格式

要破解,请使用以下格式。

第一行应包含一个奇数整数 $$$n$$$ (网格的一侧)。

$$$n$$$ 后面的第 $$$i$$$ 行应包含与网格的第 $$$i$$$ 行相对应的长度为 $$$n$$$ 的字符串。网格的左上角元素必须等于 $$$1$$$,右下角元素必须等于 $$$0$$$。

示例

输入 #1

3
0
1
0
1
1
1
1

输出 #1

? 1 1 1 3
? 1 1 2 3
? 2 1 2 3
? 3 1 3 3
? 2 2 3 3
? 1 2 3 2
? 1 2 3 3
!
100
001
000