← 返回题目列表

Codeforces · 1523/A

A. 生命游戏

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

William 非常喜欢名为“生命游戏”的元胞自动机,因此他决定制作自己的版本。为了简单起见,William 决定在包含 $$$n$$$ 个单元的数组上定义他的元胞自动机,每个单元要么是活的,要么是死的。

威廉元胞自动机中数组的演化按以下方式迭代发生:

- 如果该元素已死亡,并且在数组的当前状态下恰好有 $$$1$$$ 存活邻居,则在下一次迭代时它将变为活动状态。对于索引 $$$i$$$ 处的元素,邻居将是索引为 $$$i - 1$$$ 和 $$$i + 1$$$ 的元素。如果该索引处没有元素,则将其视为死邻居。
- 威廉是一个仁慈的人,所以所有活着的元素都活着。

检查注释部分以获取演变的示例。

给定了所有元素的一些初始状态,您需要帮助 William 在 $$$m$$$ 进化迭代后找到数组的状态。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^3$$$)。测试用例的描述如下。

每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$2 \le n \le 10^3, 1 \le m \le 10^9$$$),它们是数组中单元格的总数和迭代次数。

每个测试用例的第二行包含一个长度为 $$$n$$$ 的字符串,由字符“0”和“1”组成,并定义数组的初始状态。 “1”表示细胞存活,“0”表示细胞死亡。

保证所有测试用例的$$$n$$$总和不超过$$$10^4$$$。

输出

在每个测试用例中输出一个长度为 $$$n$$$ 的字符串,由字符“0”和“1”组成——经过 $$$m$$$ 进化迭代后数组的状态。

示例

输入 #1

4
11 3
01000000001
10 2
0110100101
5 2
10101
3 100
000

输出 #1

11111001111
1110111101
10101
000

注意

第一个测试用例的迭代演化序列

- 01000000001 — 初始状态
- 11100000011 — 进化的第一次迭代
- 11110000111 — 进化的第二次迭代
- 11111001111 — 进化的第三次迭代

第二个测试用例的迭代演化序列

- 0110100101 — 初始状态
- 1110111101 — 进化的第一次迭代
- 1110111101 — 进化的第二次迭代