文理学院程序设计在线练习


生命游戏

Time Limit: 1 Second(s)    Memory Limit: 32 MB

Total Submission(s): 55   Accepted Submission(s): 18
Problem Description

生命游戏(game of life)为1970年由英国数学家J. H. Conway所提出,是一个零玩家游戏。它包括一个二维矩形世界,这个世界中的每个方格居住着一个活着的或死了的细胞。一个细胞在下一个时刻的生死取决于相邻八个方格中活着的或死了的细胞的数量。如果相邻方格活着的细胞数量过多,这个细胞会因为资源匮乏而在下一个时刻死去;相反,如果周围活细胞过少,这个细胞会因太孤单而死去。某一细胞的邻居包括上、下、左、右、左上、左下、右上与右下相邻之细胞,游戏规则如下:

1.孤单:如果当前为活细胞,周围活细胞小于或等于一个,则该细胞在下一次状态将死亡。
2.拥挤:如果当前为活细胞,周围活细胞大于或等于四个,则该细胞在下一次状态将死亡。
3.稳定:如果当前为活细胞,周围活细胞为二个或三个,则该细胞在下一次状态将保持不变;
4.复活:如果当前为死细胞,周围活细胞为三个,则该细胞在下一次状态将复活;

如图就是生命游戏的一些变换示例,其中绿色代表存活的细胞。

注意:关于生命游戏的规则有多种版本,此处以上面的描述为准。

Input

输入数据首先包含一个整数T(1<=T<=10),表示测试实例的个数,然后是T组测试数据。
每组测试第一行包括2个整数m,n(3<=m,n<=50),表示m行n列,接下来就是 m行n列由0,1组成的矩阵,其中1表示该位置是活细胞,0表示该位置是死细胞。

Output

对于每组测试,输出下一时刻的新状态。

Sample Input
3
3 3
101
010
101
3 3
000
111
000
3 3
000
101
100
Sample Output
010
101
010
010
010
010
000
010
010
Author

flx

Source

usx第八届程序设计竞赛