「BJSS2020 J」生命游戏【无数据】
暂无测试数据。
背景
- Idea: 北京市赛
- Data: 暂无
- Std: 北京市赛
- 题面: 北京市赛+oistream
著名数学家约翰·康威(\(\text{John H. Conway,1937}\sim\text{2020}\))不幸于新冠肺炎疫情中去世。他的研究兴趣涵盖组合游戏、群论等多个领域,在有限群分类、元胞自动机和组合游戏上做出了重要的贡献;他致力于数学科普,设计了曾风靡全球的“康威生命游戏”(\(\text{Conway's Game of Life}\))。
今天,让我们来回顾他最著名的发明之一。
生命游戏的规则如下:
- 有一个正方形网格,每个格子中有一个细胞,细胞有两种状态:死亡或存活。每个细胞在下一刻的状态都由其现在的状态以及周围 \(8\) 个细胞的状态唯一确定。
- 当前细胞为存活状态时,如果它周围的存活细胞低于 \(2\) 个(不包含 \(2\) 个),该细胞变成死亡状态。
- 当前细胞为存活状态时,如果它周围有 \(2\) 个或 \(3\) 个存活细胞,该细胞保持原样。
- 当前细胞为存活状态时,如果它周围有超过 \(3\) 个存活细胞,该细胞变成死亡状态。
- 当前细胞为死亡状态时,当周围有 \(3\) 个存活细胞,该细胞变成存活状态,否则仍是死亡状态。
描述
由于计算机内存限制,我们无法模拟无限大的网格上的生命游戏,因此我们只考虑 \(4\times 4\) 网格上的生命游戏,即认为**网格外禁止细胞存活**。
接下来你有 \(Q\) 组询问,每次给你一个 \(4\times 4\) 网格上的每个格子状态。问你 \(T\) 个时刻之后网格上每个格子的状态。
输入格式
- 第一行输入一个正整数 \(Q\),表示询问组数。
- 接下来 \(5\times Q\) 行,每 \(5\) 行表示一组询问。
- 每组询问前 \(4\) 行每行一个长为 \(4\) 的
01
组成的字符串。表示这个网格上每个格子的细胞状态,其中0
表示死亡,1
表示存活;接着一行一个正整数 \(T\),表示接下来经过多少个时刻。
- 每组询问前 \(4\) 行每行一个长为 \(4\) 的
输出格式
输出 \(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\)。