AT_s8pc_6_i.Garden 2

时光回到2022年6月20日。AtCoder为庆祝公司成立十周年，在总部前建造了一个花园。
这个花园能用一个 $H$ 行 $W$ 列的网格表示，每一格的位置用 $(i, j)$ 表示，$i$ 为行号，$j$ 为列号。
每个格子中种着一朵花，花在位置 $(i, j)$ 的美丽度用 $A_{i, j}$ 表示。

例如，下图展示了一个花园，其中每个格子内的数字表示花的美丽度。

你的任务是砍掉一些花，让花园变得「美丽」。要称为「美丽的花园」，必须满足以下条件：

• 任意两朵未被砍掉的花之间的路径唯一，且路径只能由上下左右相邻的未砍掉的花组成，并且不能经过相同的格子两次。
• 上述条件对于所有未被砍掉的花对 $(a, b)$ 和 $(c, d)$ 均成立（当 $(a, b) \neq (c, d)$）。

例如，以下是一个将花园变得美丽的砍伐方式：

而以下的砍伐方式不能获得「美丽的花园」：

「花园的得分」是所有未被砍掉的花的美丽度之和。如果花园不满足「美丽」条件，得分为 $0$。
例如，上图中的花园 $A$ 得分为 $20$，花园 $B$ 得分为 $60$，而花园 $C$、$D$、$E$ 得分均为 $0$。
请输出一种砍伐方案，使得花园得分尽可能高。

输入从标准输入给出，格式如下：

$H$ $W$ $A_{1, 1}$ $A_{1, 2}$ $A_{1, 3}$ … $A_{1, W}$ $A_{2, 1}$ $A_{2, 2}$ $A_{2, 3}$ … $A_{2, W}$ $A_{3, 1}$ $A_{3, 2}$ $A_{3, 3}$ … $A_{3, W}$ … $A_{H, 1}$ $A_{H, 2}$ $A_{H, 3}$ … $A_{H, W}$

请输出 $H$ 行，每行表示花园的一个行：

$c_{1, 1}c_{1, 2}c_{1, 3}…c_{1, W}$ $c_{2, 1}c_{2, 2}c_{2, 3}…c_{2, W}$ $c_{3, 1}c_{3, 2}c_{3, 3}…c_{3, W}$ … $c_{H, 1}c_{H, 2}c_{H, 3}…c_{H, W}$

其中，如果格子 $(i, j)$ 未被砍掉则用 # 表示，砍掉则用 . 表示。

约束条件

• $H, W$ 均为 $1$ 到 $500$ 之间的整数
• $A_{i, j}$ 为 $1$ 到 $9$ 之间的整数

测试数据生成方式

测试用例如下生成：

• 每个测试用例的 $H, W$ 是固定的，具体可见子任务与得分部分。
• $A_{i, j}$ 在 $1$ 至 $9$ 之间随机生成。

子任务与得分

总计有 $15$ 个测试用例，每个案例满分 $100$ 分，总分 $1500$ 分。具体计算方法如下。设「花园得分」为 $L$，且 $L' = L \div (H \times W)$。

(☆) 当 $H = 5, W = 5$ （测试用例 $1, 2, 3$）或 $H = 5, W = 500$（测试用例 $4, 5, 6$）时

• $0.00 \leq L' < 2.00$：$0$ 分
• $2.00 \leq L' < 3.33$：$0 + (L - 2.00) \times 21$ 分
• $3.33 \leq L' < 3.93$：$28 + (L - 3.33) \times 40$ 分
• $3.93 \leq L' < 4.03$：$52 + (L - 3.93) \times 480$ 分
• $4.03 \leq L'$：$100$ 分

(★) 当 $H = 500, W = 500$（测试用例 $7$ 到 $15$）时

• $0.00 \leq L' < 2.00$：$0$ 分
• $2.00 \leq L' < 3.33$：$0 + (L - 2.00) \times 21$ 分
• $3.33 \leq L' < 3.78$：$28 + (L - 3.33) \times 75$ 分
• $3.78 \leq L' < 3.84$：$61 + (L - 3.78) \times 650$ 分
• $3.84 \leq L'$：$100$ 分

当 $2.00 \leq L'' \leq 4.05$ 时，得分随 $L'$ 的变化如下图所示：

注意事项

每当有得分为 $0$ 的测试用例时，将判定为 WA。即使得到 WA，也有可能获得部分分数；同样，即使得到 AC，也不一定满分。

由于这是一个马拉松类型的题目，不能保证所有测试用例都能得到满分。即使是出题者提供的解法也未必能获得满分。
此外，如果发现多数提交超出满分标准，可能会对得分公式进行调整，这种情况的发生概率极小。请注意，比赛开始 3 小时后，得分公式将不会再更改。

样例解释 1

按照示例输出 1 的砍伐方式，花园的得分为 $1 + 3 + 4 + 5 + 6 + 7 + 9 = 35$ 分。请注意，这个例子不在评分数据中。

样例解释 2

该输入示例对应于问题描述中的图片，而示例输出 2 对应于例子 B，花园得分为 $60$。此时 $L'$ 的值为 $60 \div 20 = 3.00$。顺便一提，也有使得花园得分达到 $62$ 的方案，但此题并不要求必须输出最大得分。请注意，这个例子也不在评分数据中。

本翻译由 AI 自动生成