AT_xmascon21_a.At Random

本题为交互题。 评测程序最多使用约 100 毫秒的运行时间和 8 MB 的内存。

有一个宽 $500$ 像素、高 $500$ 像素的画布，像素的位置由整数对 $(x,\ y)$ 表示（$0\leq x<500$，$0\leq y<500$）。**请注意，$x$ 坐标增加的方向是从左到右，$y$ 坐标增加的方向是从上到下。**每个像素要么是白色，要么是黑色。初始时，画布上的所有像素都是白色。

现在，有两只狐狸 $0$ 和 $1$，它们都拿着巨大的铅笔，站在像素 $(0,\ 0)$ 上。你需要通过最多 $10\,000$ 次操作，绘制出给定的目标设计图像。

• 操作：指定像素 $(x,\ y)$，并对狐狸说“请移动到像素 $(x,\ y)$”。然后，狐狸 $0$ 和狐狸 $1$ 中随机等概率地选择一只移动到像素 $(x,\ y)$。你可以指定已经有狐狸（无论是一只还是两只）所在的像素进行操作。

狐狸在移动时，会从移动前的像素到移动后的像素画出一条黑色的线段。具体来说，使用布雷森汉姆算法确定线段经过的所有像素，并将这些像素全部变为黑色。（详细实现可参考提供的本地测试器）

今年的招牌设计

1. 输入一行，包含三个整数 $W,H,T$，以空格分隔。
   • 这表示目标设计和画布的宽为 $W$ 像素，高为 $H$ 像素，最多可以进行 $T$ 次操作。
   • 在本题中，输入保证 $W=500$，$H=500$，$T=10\,000$。
2. 接下来 $H$ 行，每行一个仅由 . 和 # 组成的长度为 $W$ 的字符串。
   • 第 $y$ 行（$0\leq y<H$）的第 $x$ 个字符（$0\leq x<W$）表示目标设计中像素 $(x,\ y)$ 的颜色。白色用 . 表示，黑色用 # 表示。
3. 以下内容最多重复 $T$ 次：
   1. 你的程序需要输出两个整数 $x,\ y$，以空格分隔。
      • 若 $(x,\ y)=(-1,\ -1)$，表示不再进行操作，循环结束。此后不再有输入。
      • 否则，$0\leq x<W$ 且 $0\leq y<H$，表示指定像素 $(x,\ y)$ 进行操作。
   2. 操作结果中，若狐狸 $k$（$k=0,1$）移动，则输入一个整数 $k$。

请参考输入输出示例。

每次操作输出两个整数 $x\ y$，以空格分隔，并及时刷新输出流。

达成条件

目标设计是一张 $500\times500$ 的黑白图像。若通过操作生成的图像同时满足以下两个条件，则认为“符合设计”：

• 在目标设计中为黑色的像素中，生成的图像中也为黑色的像素比例不少于 $85\%$。
• 在目标设计中为白色的像素中，生成的图像中也为白色的像素比例不少于 $70\%$。

数据

**本题所需的相关数据可从这里下载。**zip 包内包含以下文件：

• atrandom/input.png：目标设计的图片。图片尺寸为 $500\times500$。
• atrandom/input.txt：目标设计按下述输入输出格式文本化的文件。实际评测时，最先输入的数据与此文件内容完全一致。
• atrandom/interactive_tester.py：用于本地测试交互的 Python 3 工具。
  • 使用方法：python3 interactive_tester.py <input_file> <seed> -- <cmd_line_solution>。
    • <input_file> 为目标设计的文本文件路径。要与实际评测一致，可使用附带的 input.txt。
    • <seed> 为决定移动狐狸时使用的随机数种子。该工具的随机数生成方式与实际评测时不一定完全一致。
    • <cmd_line_solution> 为你的解答程序的命令行字符串。
  • 例如，若你的 C++ 解答编译为 solver.out，可在同一目录下运行：python3 interactive_tester.py input.txt 0 -- ./solver.out。
  • 若你的 Python 解答为 solver.py，可运行：python3 interactive_tester.py input.txt 0 -- python solver.py。
  • 该工具中的 drawline 函数实现了布雷森汉姆算法，可供参考。
• atrandom/visualize.html：用于可视化本地测试工具输出的详细图片数据的可视化工具。
  • 本地测试工具运行后，会在同一目录下生成 interactive_tester.dump 文件。将该文件输入到可视化工具中，可查看你程序生成的图像并保存。

注意事项

所有操作结束后，你的程序必须立即退出。若未能及时退出，评测结果不确定。此外，若输出不合法，结果也不确定（不一定会返回 WA）。

所有操作结束并退出后，若生成的图像满足达成条件，则判为正确。

请注意，输出后必须立即刷新输出流。如果未刷新，可能会导致 TLE。

各语言的输入输出方法可参考 AtCoder 以往的交互题（如：ABC 019 D: 高桥君与树的直径）。

输入输出示例

以下为 $W=5,\ H=5,\ T=10$ 时的输入输出示例。

实际测试数据与提供的数据完全一致，以下仅为说明示例。

输入 输出 说明

5 5 10

给出 $W,H,T$。

..##.
.####
####.
###..
.#...

给出目标设计。

2 4

操作 $(x,\ y)=(2,4)$。

1

狐狸 $1$ 移动。

3 3

操作 $(x,\ y)=(3,3)$。

1

狐狸 $1$ 移动。

3 0

操作 $(x,\ y)=(3,0)$。

0

狐狸 $0$ 移动。

-1 -1

不再进行操作（共进行了 $3$ 次操作）。

由 ChatGPT 4.1 翻译