← 返回题目列表

AtCoder · birthday0410_b

B. 米饭游戏

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

問題文

作为享誉世界的日本玩具制造商,英语社因业绩不振而陷入了破产危机。与此同时,如今世界上使用大米制作的“米饭游戏”正掀起空前绝后的热潮!英语社当然不愿错过这场米饭游戏热潮,于是决定加大在日本的推广力度。

为了将这个游戏商品化并进行大规模生产,无论如何都需要大量的大米!这起案件的犯罪者立即“更多更多的大米,请!”联系了海外分公司,但是……。

“怎么会这样……怎么会这样……。”

几天后,总公司大量收到的却是数量惊人的虱子。面对数量恐怖的虱子而陷入绝望的员工们,以及目瞪口呆的犯罪者。为什么会发生这样的事情呢?

答案很明确。负责人… “更多!更多!请虱子!” 等令人发指的要求,海外分公司的员工毫无疑问地大量订购了虱子。也就是说,负责人的发音引发了所有的灾难。一切责任都在负责人身上。公司还不错。

没有人知道如何处理我借巨额债务获得的大量虱子。在这种破产不可避免的情况下,公司除非想办法把这些虱子转化为利润,否则肯定会破产。

这就是 Engrish 决定推出名为“虱子游戏”的东西的原因。虱子游戏是一款使用大量虱子的游戏,是一款让孩子了解生物生态的有趣游戏。

该游戏在划分为网格的培养玻璃上进行。网格中的每个单元格都有两种模式,有或没有虱子,第一天你可以将虱子放在你喜欢的任何单元格中。此后,每一代人都按照既定规则发生变化。明天某个细胞内是否有虱子取决于今天该细胞内是否有虱子以及该细胞周围有多少个细胞有虱子。然而,单元格的外围是指与该单元格共享点的八个单元格。具体规则如下。

  • 如果今天一个单元格中有虱子,并且周围有两三个单元格有虱子,那么明天这些单元格中仍然会有虱子。 (对于任何其他数量的虱子,明天该牢房中将没有虱子)
  • 如果今天某个单元格中没有虱子,但附近有 3 个单元格有虱子,则明天该单元格中将会有虱子。 (如果不是这个数字,明天这个牢房里就没有虱子了。)

这场比赛当然大受欢迎,恩格里什终于恢复了呼吸。

顺便说一句,JAPLJ先生是一名细菌恐惧症患者,所以他总是说“虱子很脏,所以不要”之类的话,并且说一些伤害生物尊严的话。我的朋友 kyuridenamida 计划将虱子游戏作为生日礼物发送给 JAPLJ,以帮助人们更多地了解虱子。

虱子游戏的麻烦之处在于,如果你随意放置虱子,它们有可能会大量繁殖。如果发生这种情况,对于 JAPLJ 来说将是可怕的。另外,如果你扔掉这个游戏,它会立即被发现,所以你千万不要扔掉它。

JAPLJ 很快发现了这一紧急情况,并正在制定对策。 JAPLJ先生想出了一个避免扔掉游戏的方法:“在第一天安排虱子,这样无论哪一天看游戏状态,虱子的位置都完全相同。”

虱子游戏附带固定数量的虱子,您必须在第一天将附着的虱子放在网格上。由于在游戏发布之前你无法知道包含了多少虱子,因此 JAPLJ 决定编写一个程序,这样无论包含多少虱子都无关紧要。

我希望你,JAPLJ 的朋友,帮我写这个程序。


課題

不用说,问题文本中的虱子游戏与康威的生命游戏具有相同的规则。因此,考虑在无限宽的网格上玩生命游戏。

在生命游戏中,我们考虑无限宽网格中每个细胞的两种状态:“生命”或“死亡”。首先,决定网格上的一些“活”细胞,并将其他细胞设置为“死”细胞。小区的下一代状态由该小区的当前状态及其相邻小区的状态决定。与某个单元格相邻的单元格是与该单元格共享点的八个单元格。具体规则如下。

  • 相邻细胞中具有两个或三个“原始”细胞的“原始”细胞将在下一代中保留为“原始”细胞。 (否则下一代就会成为“死亡”细胞)
  • 相邻细胞中恰好有三个“活”细胞的“死”细胞在下一代中将成为“活”细胞。 (否则即使到了下一代,它仍然是一个“死”细胞)

维基百科上的《生命游戏》文章也有类似的规则,请参考。

一些“原始”单元的排列在 8 个方向上连接,这意味着通过仅跟踪相邻的“原始”单元,可以从任何其他“原始”单元到达任何“原始”单元。N “原始”细胞在8个方向上连接,并且无论经过多少代,排列都保持完全相同(即一开始是“原始”的细胞) 编写一个程序,找到一个细胞,使 N 细胞保持“活着”,而所有其他细胞保持“死亡”。


入力

N

N 表示“原始”单元格的数量。 对于

出力

S_1
S_2
…
S_N

1 \leq i \leq N 反对 S_i 是 它仅由 N 一串字符,其中每个字符代表单元格的状态。这个 N 串在无限宽的网格中。 将其视为提取 N \times N 部分。 它仅由两种类型的字符组成:

各 S_i 是 它仅由 . 或 替换为 # ,. 表示该单元处于“死亡”状态,# 表示单元处于“原始”状态。S_i 中包含的字符 # 的总数是 必须是 N 。还有人物 # 必须在 8 个方向上连接。

但是,如果没有满足条件的“原始”单元格排列,则仅输出 -1。


制限

所有输入数据满足以下约束。 如果您对满足

  • 1 \leq N \leq 1,000

採点基準

  • N \leq 8 的所有输入数据回答正确 给出 1 点。
  • 如果您对所有输入数据都回答正确,则 99 点。

入力例1

4

出力例1

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

入力例2

1

出力例2

-1

作者:JAPLJ
声明:kyuridenamida