AT_ahc050_a [AHC050A] Gamble on Ice

有一个由 $N \times N$ 个格子组成的溜冰场。左上角格子的坐标为 $(0,0)$，向下移动 $i$ 格、向右移动 $j$ 格的位置坐标为 $(i,j)$。$N \times N$ 格子的外部全部被岩石包围，无法进入。初始状态下，有 $M$ 个格子上放置了岩石。 你需要利用这个溜冰场和一个机器人进行如下游戏： - 游戏开始时，你的奖金为 $0$ 元。 - 首先，你需要声明一个由未被岩石占据的 $N^2-M$ 个格子按任意顺序排列的序列 $P=(P_0,P_1,\dots,P_{N^2-M-1})$。 - 接着，从未被岩石占据的格子中随机等概率选取一个，放置机器人。 - 然后，依次对 $i=0,1,\dots,N^2-M-1$ 执行以下操作： - 首先，机器人从上下左右四个方向中随机等概率选择一个方向。 - 然后，机器人沿该方向直线移动，直到撞到岩石为止。 - 注意，机器人有可能一个格子都不移动。 - 随后，在格子 $P_i$ 上放置岩石。 - 如果机器人正好在该格子上，机器人会被压扁，游戏结束。 - 如果机器人不在该格子上，你获得 $1$ 元奖金。 请你求出能使最终期望奖金尽可能大的序列 $P$。

输入通过标准输入给出，格式如下： > $N$ $M$ > $S_{0,0}\ S_{0,1}\ \dots\ S_{0,N-1}$ > $\vdots$ > $S_{N-1,0}\ S_{N-1,1}\ \dots\ S_{N-1,N-1}$ - 所有测试点中，$N=40$。 - $M$ 是 $N^2/10$ 以上、$N^2/4$ 以下的整数。 - $S_{i,0}\ S_{i,1}\ \dots\ S_{i,N-1}$ 是由 `#.` 组成的 $N$ 个字符的字符串，$S_{i,j}$ 为 `#` 表示初始状态下格子 $(i,j)$ 上有岩石，为 `.` 表示初始状态下格子 $(i,j)$ 上没有岩石。

你需要输出你求得的序列 $P$，其中 $P_i=(x_i,y_i)$，输出格式如下： > $x_0$ $y_0$ > $\vdots$ > $x_{N^2-M-1}$ $y_{N^2-M-1}$ 此时，序列 $P$ 必须满足以下约束： - 所有 $P_i$ 互不相同。 - 对所有 $P_i$，初始状态下格子 $P_i$ 上没有岩石。

### 得分 设最终获得的奖金期望为 $E$，则得分为 $\displaystyle {\rm round}\left(\frac{10^6 \times E}{N^2-M-1}\right)$。 共有 150 个测试用例，所有测试用例得分之和为你的提交得分。如果有一个及以上的测试用例输出不合法或超时，则整份提交判为 WA 或 TLE。比赛期间以最高得分计入最终排名，赛后不再进行系统测试。若多名参赛者得分相同，则排名并列。 ### 输入生成方法 - 首先，$N=40$。 - 然后，$M$ 从 $N^2/10$ 到 $N^2/4$ 的整数中等概率随机选取。 - 最后，从 $N^2$ 个格子中随机选取 $M$ 个不同的格子放置岩石，确定初始状态。 ### 工具（输入生成器与可视化器） - [网页版](https://img.atcoder.jp/ahc050/k1BmZE1o.html?lang=ja)：比本地版更高性能，支持动画显示和手动游玩。 - [本地版](https://img.atcoder.jp/ahc050/k1BmZE1o.zip)：需安装 [Rust 语言](https://www.rust-lang.org/ja) 编译环境。 - [Windows 版已编译二进制](https://img.atcoder.jp/ahc050/k1BmZE1o_windows.zip)：不想配置 Rust 环境可直接使用。 比赛期间禁止分享可视化结果、解法或思路等相关内容，请注意遵守规则。 由 ChatGPT 4.1 翻译