/ / 题库 /

「BJSS2020 J」生命游戏【无数据】

「BJSS2020 J」生命游戏【无数据】

测试数据来自 oistream/1140

背景

  • Idea: 北京市赛
  • Data: 暂无
  • Std: 北京市赛
  • 题面: 北京市赛+oistream

著名数学家约翰·康威(\(\text{John H. Conway,1937}\sim\text{2020}\))不幸于新冠肺炎疫情中去世。他的研究兴趣涵盖组合游戏、群论等多个领域,在有限群分类、元胞自动机和组合游戏上做出了重要的贡献;他致力于数学科普,设计了曾风靡全球的“康威生命游戏”(\(\text{Conway's Game of Life}\))。

今天,让我们来回顾他最著名的发明之一。

生命游戏的规则如下:

  1. 有一个正方形网格,每个格子中有一个细胞,细胞有两种状态:死亡或存活。每个细胞在下一刻的状态都由其现在的状态以及周围 \(8\) 个细胞的状态唯一确定。
  2. 当前细胞为存活状态时,如果它周围的存活细胞低于 \(2\) 个(不包含 \(2\) 个),该细胞变成死亡状态。
  3. 当前细胞为存活状态时,如果它周围有 \(2\) 个或 \(3\) 个存活细胞,该细胞保持原样。
  4. 当前细胞为存活状态时,如果它周围有超过 \(3\) 个存活细胞,该细胞变成死亡状态。
  5. 当前细胞为死亡状态时,当周围有 \(3\) 个存活细胞,该细胞变成存活状态,否则仍是死亡状态。

描述

由于计算机内存限制,我们无法模拟无限大的网格上的生命游戏,因此我们只考虑 \(4\times 4\) 网格上的生命游戏,即认为**网格外禁止细胞存活**。

接下来你有 \(Q\) 组询问,每次给你一个 \(4\times 4\) 网格上的每个格子状态。问你 \(T\) 个时刻之后网格上每个格子的状态。

输入格式

  • 第一行输入一个正整数 \(Q\),表示询问组数。
  • 接下来 \(5\times Q\) 行,每 \(5\) 行表示一组询问。
    • 每组询问前 \(4\) 行每行一个长为 \(4\) 的 01 组成的字符串。表示这个网格上每个格子的细胞状态,其中 0 表示死亡,1 表示存活;接着一行一个正整数 \(T\),表示接下来经过多少个时刻。

输出格式

输出 \(4\times Q\) 行,每 \(4\) 行表示一组询问对应的答案。

每组询问的答案,每行一个长为 \(4\) 的 01 组成的字符串。表示这个网格上每个格子的细胞状态,其中 0 表示死亡,1 表示存活。

样例

输入样例1

1
0000
1100
0110
0000
3

输出样例1

0100
1010
1010
0100

样例解释1

经过一个时刻后,网格状态变为

0000
1110
1110
0000

再经过一个时刻后,网格状态变为

0100
1010
1010
0100

然后下一个状态会与该状态相同,也就是说接下来的时刻永远都会保持这一状态。因此从开始经过 \(3\) 个时刻后是该状态。

输入样例2

见附加文件。

输出样例2

见附加文件。

数据规模与约定

对于 \(100\%\) 的数据,保证 \(Q\leq 10^4, T\leq 10^9\)。

捕获2.JPG

信息

ID
2605
难度
(无)
分类
模拟 | 字符串 点击显示
标签
递交数
0
已通过
0
通过率
?
上传者